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 inaveragecase for list with 8 elements? ______________ How many comparisons inaveragecase for list with 1,000,000 elements? _____________ How many comparisons inaveragecase 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 inworstcase for list with 8 elements? ______________ How many comparisons inworstcase for list with 1,000,000 elements? _____________ How many comparisons inworstcase 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?