Version 5.2.1¹

Handouts: BinarySearch.java.

A. Searching

Two methods for searching arrays.

8.1 Linear Search

• Naive version: start at the beginning of the list, examine successive elements; stop when you find it or reach the end of the array.
  • Example: in the array [7, 3, 9, 5, 1], search for 5; search for 2.
• Improved version, for sorted arrays: stop also when you reach the first element greater than the search target.
  • Example: in the array [1, 3, 5, 7, 9], search for 5; search for 2.
  • Code: Fig. 8-1, p. 206

8.2 Binary Search

• For sorted data only.
• The idea
• Example: in [1, 3, 5, 7, 9], search for 5, 7, and 2.
• Code: Fig. 8-3, p. 208 (iterative version) [skip]
• The algorithm is naturally recursive, so here's an alternative, recursive implementation: BinarySearch.java. This, like the code in Fig. 8-3, works for arrays of int.
• Analysis: Each step of the search divides the search space in half. Divide N by 2, repeating log₂ N times, and you get 1. (This works exactly when N is a power of 2, and approximately otherwise. Compare: start with 1, double the number k times, and you get 2^k. So if 2^k = N, then k = log₂ N.) When the search space size is 1, we are done, either success or failure. So for a sorted array of size N, in the worst case, binary search has running time Θ(log N).
  • Note: the exponential and logarithmic functions, 2^N and log₂ N, are inverse functions, just as + and -,
  • and / are inverse functions.
• How good is this? For array sizes of a thousand, a million, and a billion, linear search requires in the worst case a thousand, a million, and a billion steps. Binary search requires only 10, 20, and 30 steps! (2¹⁰ = 1024, etc.)

The Big Idea

Whenever we can reduce a problem's size by halving it instead of subtracting one, we get a big gain: we reduce a factor of N to a factor of log N.

Examples:

• Reduction of Θ(N) to Θ(log N)
• Θ(N²) to Θ(N log N)
• Θ(N⁵) to Θ(N^4 log N)

B. Sorting

8.3 Insertion Sort

• Sorting an array.

• The idea:

                 Current element
                        |
                        V
  +--------------------+--+-----------------------------+
  |sorted region       |  | unsorted region             |
  +--------------------+--+-----------------------------+

  For each element from first to last: insert the element into the correct position in the sorted region, increasing that region's size by one. The sorted region is initially just a single element, xs[0]; at the end, it is the entire array.
• Example: sort the array [7, 3, 9, 5, 1] ...
• Code: Fig. 8-8, p. 212 (for arrays of int) (file: Search.java)
• Analysis:
  1. The outer loop repeats N − 1 times.
  2. The inner loop, for the ith element, counting down from i − 1, repeats:
     • (best case: already sorted) 1 time, Θ(1).
     • (worst case: reverse order) i times, i ≤ N, Θ(N).
     • (average case: random order) i/2 times, i/2 ≤ N, Θ(N).
  3. The total time is the number of repetitions of the outer loop times the number of repetitions of the inner loop:
     • best case: Θ(N) — nice for an "almost sorted" array
     • worst case: Θ(N²)
     • average case: Θ(N²) (but with a lower constant factor).
  4. The constant factor is small, so this technique is efficient for small arrays. Yes, he really said that.

Dance

Insert-sort with Romanian folk dance (YouTube, 4:04)

8.4 The Comparable Interface

• Accent the first syllable: com-parable
• For classes of object that can compare themselves, in the sense of "I am less than, equal to, or greater than that."
• Allows us to "generalize" from arrays of int, to arrays of any type of object for which comparison makes sense.²
• The compareTo method: a.compareTo(b) returns:
  1. An unspecified negative integer if a < b
  2. Zero if a is equal to b. (Should agree with the equals method.)
  3. An unspecified positive integer if a > b Does not necessarily return −1, 0, or +1.
• For three-way decisions, e.g. in binary search, make the comparison once, and save the value to avoid recomputing it; it could be an expensive computation.
• On the other hand, it could be as simple as subtraction, as for the Die class example (Die.java, p. 217). Note that this implementation would be likely to return a value other than −1 or 1, for unequal values.
• The interface is generic: Comparable<T>, since an object of type T can be expected to compare itself only to objects of the same type: numbers to numbers, strings to strings, dice to dice, for example.
• Classes which implement Comparable include: Boolean, Character, Double, Integer, String; but not Object.

• Using the interface for searching and sorting arrays of comparable elements: declare the elements <E extends Comparable<E>> (why?), for example,

  public class SortableArrayList<E extends Comparable<E>> {
    ...
  }

  (see SortableArrayList.java, SortableLinkedList.java)

• Exercise: modify the recursive binary search for an array of Comparable (say String or Integer) objects.

8.5 Sorting Linked Lists

• The techniques for sorting arrays, such as insertion sort, can frequently be adapted to sort linked lists.
• In the example (SortableLinkedList.insertionSort, Fig. 8-17, p. 219), he first creates a new, empty list and starts inserting elements into it. Why?
• Could also be done using the recursive, reconstructive approach to lists, but we omit the details.

Retrospect

• Is it worth while to sort before binary search?
• How can we keep the list in sorted order, when inserting new elements?

Footnotes