Algorithms/Search

Notes

Goodrich chapter 4

Binary Search Analysis

Recursion: binary search analysis.

Proposition: The binary search algorithm runs in O(log n) time for a sorted sequence with n elements.

Justification: To prove this claim, a crucial fact is that within each recursive call the number of candidate entries still to be searched is given by the value

high - low + 1

Moreover, the number of remaining candidates is reduced by at least one half with each recursive call. Specifically, from the definition of mid, the number of remaining candidates is either

$ (mid - 1) - low + 1 = floor( \dfrac{low+high}{2} ) - low \leq \dfrac{high - low + 1}{2} $

or,

$ high - (mid+1) + 1 = high - floor( \dfrac{low + high}{2} ) \leq \dfrac{high - low + 1}{2} $

Initially, n candidates; next call, n/2 candidates; next call, n/4 candidates; etc. The maximum number of recursive calls is the smallest integer r such that:

$ \dfrac{n}{2^r} < 1 $

In other words, $ r > \log{(n)} $

Thus, we have

$ r = floor( \log{(n)} ) + 1 $

which implies that binary search runs in O(log N) time.

Skiena Chapter 4

Binary Search

Binary search is a fast algorithm for finding a key k in a sorted array S of keys. Binary search begins by looking at the middle key. If it is less than the target, it repeats the process on the second half of the array instead of the entire array; if it is larger than the target, it repeats the process on the first half of the array. It proceeds until it is examining a single element, in which case it either finds the key or not.

Counting occurrences of a key in a sorted array can be done with binary search in two ways:

• Use a binary search to find the first occurrence of the key k, then count until you reach a different key. This takes O(log n + r) time, where r is the number of records with identical keys.
• Use a binary search to find the first occurrence of the key k, then use another binary search, modified to have no equality check and move right if it does not explicitly move left, to find the right boundary.

Overall, counting occurrences takes log time, regardless of size of run of identical keys (so, e.g., worst case 90% of your keys are the same, this algorithm won't break a sweat).

Finding Greatest Element Less Than/Least Element Greater Than Key

The modification mentioned above can be generalized as follows: we can modify the binary search procedure so that it will return the greatest key less than a specified key, or the least key greater than a specified key, by removing the equality and implementing the comparison in the correct way. For example:

binary search(data, key, lo, hi):
    int middle
    if( low > high):
        return -1 // key not found
    mid = (lo + hi)/2
    // if( data[mid] equals key) 
    //     return mid // we remove this for our purposes

    // if we want to move right by default:
    if( data[mid] > key ):
        return binary search(data, key, lo, mid-1)
    else
        return binary search(data, key, mid+1, hi)

    // if we want to move left by default:
    if( data[mid] < key ):
        return binary search(data, key, mid+1, hi)
    else
        return binary search(data, key, lo, mid-1)

One-Sided Binary Search

a modified binary search.