Handout 10

Binary Search*

---

Introduction

A binary search algorithm (or binary chop) is a technique for finding a particular value in a linear array, by ruling out half of the data at each step. A binary search finds the median, makes a comparison to determine whether the desired value comes before or after it, and then searches the remaining half in the same manner. A binary search is an example of a divide and conquer algorithm.

Algorithm

function binarySearch(a, value, left, right)
    if right < left
        return not found
    mid := floor((left+right)/2)
    if value > a[mid]
        return binarySearch(a, value, mid+1, right)
    else if value < a[mid]
        return binarySearch(a, value, left, mid-1)
    else
        return mid

function binarySearch(a, value, left, right)
    while left <= right
        mid := floor((left+right)/2)
        if value > a[mid]
            left  := mid+1
        else if value < a[mid]
            right := mid-1
        else
            return mid
    return not found

In both cases, the algorithm terminates because on each recursive call or iteration, the range of indexes right minus left always gets smaller, and so must eventually become negative.

Binary search is a logarithmic algorithm and executes in O(log n) time. Specifically, 1 + log2N iterations are needed to return an answer. It is considerably faster than a linear search. It can be implemented using recursion or iteration, as shown above.

Tail Recursion

In computer science, tail recursion (or tail-end recursion) is a special case of recursion that can be easily transformed into an iteration. Such a transformation is possible if the recursive call is the last thing that happens in a function. Replacing recursion with iteration, either manually or automatically, can drastically decrease the amount of stack space used and improve efficiency. This technique is commonly used with functional programming languages.