1.You can perform a sequential search over the array using a loop, or you can sort the array using Arrays.sort and then perform a binary search over it using Arrays.binarySearch.

2.Closest value to the number of elements that the binary search algorithm will need to examineon an array of one million integers:

3. e
4. A sequential search must be used on an array of Point objects because they do not implement Comparable.

5. Arrays.binarySearch and Collections.binarySearch can be used successfully if the array or collection contains elements that are sorted, according to either their natural ordering or the ordering of a Comparator.

6. Collections.sort on a list of strings would arrange them in alphabetical order, case-sensitive. To change the order, you could pass a Comparator that defines a different order.

7. Collections.sort would not work on a list of Point objects by default because they do not implement the Comparable interface. To make it work, you could pass a Comparator that defines an ordering for Points.

8. The AccountComparator shown has a few errors:

9.line 2: It should implement Comparator rather than just Comparator.
line 3: The method should be named compare, not compareTo. It should also accept two BankAccount parameters, not just one.
lines 5,7: The code should refer to the two parameters passed in, not this.
line 7: You cannot return the subtraction of two doubles from a compare method. The result must be of type int, and it must still work even if the accounts differ only by a few cents.
Here is a corrected version of the code:

10.We could easily reverse the order of our LengthComparator by using the built-in method Collections.reverseOrder, which accepts a Comparator and returns a new one with the opposite order of the one passed in.

11. O(log N)

12. O(N)

13. O(N2)

14. O(N2)

15.O(N)

16.Complexity classes of the given algorithms in terms of N:

O(N)
O(N2)
O(N)
O(N)
O(log B)
O(N3)
O(N)
O(N)
17.Complexity classes of the given statements:

O(N log N)
O(N2)
O(N2 log N)
O(N)
O(1)
O(N)
O(N!)
The runtime complexity of both sequential searches is O(N).

17.Binary search requires a sorted dataset because it uses the ordering to jump to the next index. If the elements are out of order, the search isn't guaranteed to find the target element.

18.A binary search of 60 elements examines at most 6 elements, because log2 60 (when rounded up) equals
13.3
19.
a.The algorithm will examine index 4 and will return 4.
b.The algorithm will examine indexes 4 and 6 and will return 6.
c.The algorithm will examine indexes 4, 6, and 7 and will return 7.
d.The algorithm will examine indexes 4, 2, 1, and 0 and will return 0.
20.The algorithm will examine indexes 4, 6, and 5 and will return -1. The algorithm doesn't work properly because the input array isn't sorted.
21.
42: examines 7, 11, 9; returns 9
11: examines 7, 3, 4; returns -5
74: examines 7, 11, 13, 14; returns 14
30: examines 7, 3, 5, 6; returns -8
22.
-5: examines 6, 2, 4, 3; returns -4
0: examines 6; returns 6
11: examines 6, 10, 8, 9; returns -10
-100: examines 6, 2, 0; returns -1
24.
d. [-4, 17, 3, 94, 46, 8, 29, 12]
13.4
26.
 merge sort of 32 elements will generate 63 total calls to mergeSort and will perform the merge operation 31 times.
27.
a.
[1, 2, 3, 4, 5, 11, 9, 7, 8, 10]
b.
[7,   2,   8,   4,   1,   11,   9,   5,   3,   10]
[7,   2,   8,   4,   1], [11,   9,   5,   3,   10]
[7,   2], [8,   4,   1], [11,   9], [5,   3,   10]
[7], [2], [8], [4,   1], [11], [9], [5], [3,   10]
               [4], [1],                 [3], [10]
          [8], [1,   4],            [5], [3,   10]
[2,   7], [1,   4,   8], [9,   11], [3,   5,   10]
[1,   2,   4,   7,   8], [3,    5,   9,  10,   11]
[1,   2,   3,   4,   5,   7,    8,   9,  10,   11]
28.
[-3, -1, 1, 2, 4, 8, 7, 21, 12, 30, 6, 9]
29.b.