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:

def binary_search(data, key, lo, hi):

    if( low > high):
        return -1 // key not found

    mid = (lo + hi)/2

    // if( data[mid] == 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

Another modification that can be made to the binary search procedure is an expanding search window that doubles with each step. This is a useful procedure if you are at a particular point and you are searching for a neighboring key.

Start by looking at the next item over, data[i+1], and performing a check if it is greater than the search key. If not, look two items over, data[i+2], and see if that key is greater than the search key. If not, look at data[i+4], then data[i+8], then data[i+16], and so on.

Once a key greater than the search key is found, you have your search range, i to i+X, where X is a power of 2. You can now call binary search using those as your low and high indices, and find your key.

The cost of this one-sided search is maximum 2 log p comparisons, where p is the width of the interval.

Modifications to Binary Search Algorithm

We can make modifications to the binary search algorithm to perform other useful tasks like counting duplicates. See Binary Search Modifications page.