2 5 3 9 1 7 8 4 How many comparisons to find 7? ______ How many comparisons to find 2? ______ How many comparisons to find 4? ______ How many comparisons to not find 6? ______ What is the best case? ___________________ What is the worst case? __________________ How many comparisons in average case for list with 8 elements? ______________ How many comparisons in average case for list with 1,000,000 elements? _____________ How many comparisons in average case for list with n elements? _______________ How could we improve searching???
1 2 3 4 5 7 8 9 How many comparisons to find 7? ______ How many comparisons to find 2? ______ How many comparisons to find 4? ______ How many comparisons to not find 6? ______ What is the best case? ___________________ What is the worst case? __________________ How many comparisons in worst case for list with 8 elements? ______________ How many comparisons in worst case for list with 1,000,000 elements? _____________ How many comparisons in worst case for list with n elements? _______________ What is the drawback to this method???
When is it best to use Linear Search? ______________________ When is it best to use Binary Search? ______________________
public static boolean search(int[] array, int toBeFound) {
1 2 3 4 5 7 8 9
public static boolean search(int[] array, int toBeFound) {
if (array.length == 0)
return false;
int first = 0;
int last = array.length - 1;
int mid;
while (first <= last) {
mid = (last - first)/2 + first;
if (toBeFound == array[mid])
return true;
else if (toBeFound > array[mid])
first = mid + 1;
else
last = mid - 1;
}
return false;
}
What test cases should we use to test the code?