Sort And Searching

The alternative to using binary search is to guess 0, then 1, then 2, then 3, and so forth, until hitting the hidden number. We refer to such an algorithm as a brute-force algorithm: it seems to get the job done, but without much regard to the cost (which might prevent it from actually getting the job done for large problems). In this case, the running time of the brute-force algorithm is sensitive to the input value, but could be as much as N and has expected value N/2 if the input value is chosen at random. Meanwhile, binary search is guaranteed to use no more than lg N steps.

Yes. The Java library java.util.Arrays contains the methods Arrays.sort() and Arrays.binarySearch() that implement mergesort and binary search for Comparable types and a sorting implementation for primitive types based on a version of the quicksort algorithm, which is faster than mergesort and also sorts an array in place (without using any extra space). SystemSort.java illustrates how to use Arrays.sort().

At the very least, the library should cutoff to some guaranteed N log N algorithm if it "realizes" it is in trouble. Perhaps to avoid side effects. Programmers may want their libraries to be deterministic for debugging. But the library only uses quicksort for primitive types when stability is not an issue, so the programmer probably wouldn't notice the randomness, except in running time.

Quick sort is a divide-and-conquer method for sorting. It works by partitioning an array of elements into two parts, then sorting the parts independently. As we shall see, the precise position of the partition depends on the initial order of the elements in the input file.

The crux of the method is the partitioning process, which rearranges the array to make the following three conditions hold:

✰ The element a[i] is in its final place in the array for i.

✰ None of the elements a[left], ..., a[i-1] is greater than a[i].

✰ None of the elements in a[i+1], ..., a[right] is less than a[i].

Given a database of all tolls collected in NJ road system, devise a scheme to answer queries of the form: extract sum of all tolls collected in a given time interval. Use a Toll data type that implements the Comparable interface, where the key is the time that the toll was collected.

An array is bitonic if it is comprised of an increasing sequence of integers followed immediately by a decreasing sequence of integers. Given a bitonic array a of N distinct integers, describe how to determine whether a given integer is in the array in O(log N) steps. Hint: find the maximum, then binary search in each piece.