# 20 - Searching

1. One of the strengths of computers is their ability to find things quickly. This ability is called ________.

sorting

mixing

lending

searching

2. Sequential or Linear search typically starts at the first element in an array or ArrayList and looks through all the items one by one.

TRUE

FALSE

3. Binary search can only be used on data that has been _____________________.

duplicated for security purposes

stored in index numbers that do not exceed 100

stored in a random order

sorted or stored in order

4. A Linear search can also operate only on data that is in order.

TRUE

FALSE

5. A Binary Search checks the ______________________is less than, equal, or greater than the desired value and then based on the results of that it narrows the search.

middle of the data to see if that middle value

first value of the data to see if that first value

last value of the data to see if that last value

second last value of the data to see if that second last (length-1) value

6. Sequential search is also called a _____________search.

linear

binear

sorting

binary

7. Sequential search is the only method that can be used to find a value in _________________.

a linear binary tree

a sorted list

a sorted sublist

an unsorted list

8. Which of the following statements is correct, regarding the following code?
```public class ListSearcher
{

/** Finds the index of a value in an array of integers.
* @param elements an array containing the items to be searched.
* @param target the item to be found in elements.
* @return an index of target in elements if found; -1 otherwise.
*/
public static int xSearch(int[] elements, int target)
{
for (int j = 0; j < elements.length; j++)
{
if (elements[j] == target)
{
return j;
}
}
return -1;
}

public static void main(String[] args)
{
int[] numArray = {3, -2, 9, 38, -23};
System.out.println("Tests of sequentialSearch");
System.out.println(xSearch(numArray,3));
System.out.println(xSearch(numArray,9));
System.out.println(xSearch(numArray,-23));
System.out.println(xSearch(numArray,99));
}

}
```

It is the code for either a linear or binary search

It is the code for a linear search

It is the code for a binary search

it is the code for a linear sort (not a search)

9. Which of the following statements is correct, regarding the following code?
```import java.util.*;

public class ArrayListSearcher
{

/** Finds the index of a value in an ArrayList of integers.
* @param elements an array containing the items to be searched.
* @param target the item to be found in elements.
* @return an index of target in elements if found; -1 otherwise.
*/
public static int sequentialSearch(ArrayList elements, int target)
{
for (int j = 0; j < elements.size(); j++)
{
if (elements.get(j) == target)
{
return j;
}
}
return -1;
}

public static void main(String[] args)
{
ArrayList numList = new ArrayList();
System.out.println("Tests of sequentialSearch");
System.out.println(sequentialSearch(numList,3));
System.out.println(sequentialSearch(numList,9));
System.out.println(sequentialSearch(numList,-23));
System.out.println(sequentialSearch(numList,99));
}

}```

All of the options here are correct, with regard to the code

The code is demonstrating a linear search.

The code here shows the use of an ArrayList as opposed to an array

.size() and get(i) is used with ArrayLists instead of length and [i] which are used in arrays.

10. Which will cause the longest execution of a sequential search looking for a value in an array of integers?

The value isn't in the array

The value is in the middle of the array

The value is the first one in the array

The value is the last one in the array

11. Which will cause the shortest execution of a sequential search looking for a value in an array of integers?

The value is the first one in the array

The value is in the middle of the array

The value isn't in the array

The value is the last one in the array

12. It is also possible to look for a string in an array or list. But, when you look for a string be sure to use == rather than equals.
```Remember that == is only true when the two references refer to the same object,
while equals returns true if the characters in the two objects are the same.
```

FALSE

TRUE

13. Binary search calculates the_______________ where left starts out at 0 and right starts out at the array length - 1 (the index of the last element).

left index as left + middle / right

middle index as left + right / 2

None of these options are correct

right index as left + right / middle

14. Consider the following code for a binary search and the different tests at the bottom of the code. What is test 2 likely to be for?
```public class SearchTest
{
public static int binarySearch(int[] elements, int target) {
int left = 0;
int right = elements.length - 1;
while (left <= right)
{
int middle = (left + right) / 2;
if (target < elements[middle])
{
right = middle - 1;
}
else if (target > elements[middle])
{
left = middle + 1;
}
else {
return middle;
}
}
return -1;
}

public static void main(String[] args)
{
int[] arr1 = {-20, 3, 15, 81, 432};

// test1 when the target is in the middle
int index = binarySearch(arr1,15);
System.out.println(index);

// test2 ____________________________________
index = binarySearch(arr1,-20);
System.out.println(index);

// test3 when the target is in the array - last
index = binarySearch(arr1,432);
System.out.println(index);

// test4 when the target is not in the array
index = binarySearch(arr1,53);
System.out.println(index);
}
}
```

when the target is the first index number

when the target is the whole array

when the target is the first item in the array

when the target is the last -1 item in the array

15. Binary search is much slower than linear search, especially on large data sets, but it can only be used on sorted data.

FALSE

TRUE

16. Often with runtimes, computer scientist think about the ________ behavior. With searching, the ___________ is usually if you cannot find the item.

worst case

lower case

instant case

best case

17. Which will cause the shortest execution of a binary search looking for a value in an array of integers?

The value is the last one in the array

The value isn't in the array

The value is in the middle of the array

The value is the first one in the array

18. Which of the following conditions must be true in order to search for a value using binary search?
```I. The values in the array must be integers.
II. The values in the array must be in sorted order.
III. The array must not contain duplicate values.```

I and II

I only

II only

II and III

19. How many times would the loop in the binary search run for an array int[] arr = {2, 10, 23, 31, 55, 86} with binarySearch(arr,55)?

2

1

4

3

20. If you had an ordered array of size 500, what is the maximum number of iterations required to find an element with binary search?

approximately 9 times

approximately 15 times

500 times

2 times