SUNY Geneseo Department of Computer Science

Correctness of Binary Search

Previous Lecture

Misc

Return tests

Questions?

Binary Search

    boolean search( A, x, low, high )
        if ( low <= high )
            mid = (low + high) / 2
            if ( A[mid] < x )
                return search( A, x, mid+1, high )
            else if ( A[mid] > x )
                return search( A, x, low, mid-1 )
            else
                return true
        else
            return false

Correctness

• Prove that if x lies between low and high in A, BinarySearch(A,x,low,high) returns true, otherwise BinarySearch(...) returns false
• Induction on n,
  • where n = size of array section
  • = high - low + 1
• Base case, n = 0
  • high must be less than low
  • Algorithm returns false
  • Which is correct because x can't be in empty section of array
• Induction hypothesis
  • Assume that for section of size < k (k >= 1), BinarySearch(A, x, low, high) returns true if x in section, otherwise it returns false.
  • Strong induction
• Show BinarySearch(A, x, low, high) in a section of k elements returns true if x in section, otherwise it returns false.
  • In this section of k elements, BinarySearch executes recursive case
  • Compares A[mid] to x
  • Case1: A[mid] < x
    • Since A sorted, x must be between positions mid+1 and high,
    • ...Which is searched recursively
    • ...Which returns true or false correctly by induction hypothesis
  • Case 2: A[mid] > x
    • By similar reasoning, x must be between positions low and mid-1, which are correctly searched recursively
  • Case 3: A[mid] = x
    • Algorithm returns true, which is correct because x is clearly in the array section
  • Sections from mid+1 to high or low to mid-1 have less than k elements, so search in them (i.e., the recursive searches) will work
• mid has to be between low and high for recursion to work on smaller sections, but otherwise its computation never affected proof

Efficiency

• Computation of mid is important here
• Efficiency depends on where x is and on size of section (n)
• Count how many time "low <= high" is executed
• Best case: find x in middle of section
• Worst case
• How accurate is time analysis? Can it really ignore the fact that there are more statements in one arm of the "if low <= high" conditional than in the other? Are any differences in execution time between the arms observable?

Next

Finish efficiency analysis of Binary Search

Read Section 9.2.2 of text as follow-up to discussion above re what needs to be counted to analyze execution time.

Next Lecture