Write SearchCompare. Read n and build the sorted array 1, 4, 7, … (a[i] = 3i + 1). For each key until the end of input, run a linear search and a binary search, both counting key comparisons (one per array element examined), and print the index found (−1 if absent) and both counts. Then print the totals and the worst case of binary search for this n (the number of times n can be halved until 0).
State the loop invariant of your binary search in a comment.
For the input
1000 1 2998 1501 5 2999
the program prints
Array: 1000 sorted values from 1 to 2998
key 1: index 0, linear 1, binary 9
key 2998: index 999, linear 1000, binary 10
key 1501: index 500, linear 501, binary 9
key 5: index -1, linear 1000, binary 10
key 2999: index -1, linear 1000, binary 10
Total comparisons: linear 3502, binary 48
Binary search worst case for n = 1000: 10 comparisons