Binary Search

Binary search is one the simplest search algorithms(most are pretty simple) to implement. However, first it assumes an important property of an array that isn't always true; the array is sorted. This search is based on the number of elements(length), and we fold the array in half each time, which makes search time logarithmic.

First, you see in the diagram above that the list is already sorted. Next, we label the first index as the lowest number(LO), the last index as the highest number(HI), and the middle index as the index between lowest and highest(MID). Keep in mind that these are just markers for indices and we aren't moving any of the array elements around.

In the diagram that's searching for the number 16 and we realize that the number 16 is smaller than the number in index MID. As a result, we move the high index right before the mid index, and we reorganize the mid index as the middle of lo and hi again. This is what cuts the array in half, and in another half every time it checks MID. The resulting indices is represented in the second row of the diagram.

The last row of the diagram, just shows that when we check MID again here we find that it matches our search number, and thus re return the MID index and we are doneeeeee!!!!

In the case that the number we are searching for is higher than MID, then we'd move LO right after MID and re-position MID. Also, in the case that we don't find any numbers, we'd just return -1.

We repeat these steps several times, folding HI and LO in halves until we've either found our number or we've looked through all the possible index elements.

Here's how it would look in java:

import java.util.Arrays;

class BinarySearch{
.
.
.
    public static int rankIndices(int key, int[] a){
        //assume here that the array is sorted already
        int lo = 0; //index 0 is lowest
        int hi = a.length - 1;                      //and the last index is highest
        while(lo <= hi){                         //stop when hi and lo have become the same index number
            int mid = lo + (hi - lo) / 2;           //find the middle of hi and lo
            if (key < a[mid]) hi = mid - 1;      //key is between mid and lo, move hi before mid
            else if (key > a[mid]) lo = mid + 1; //key is between mid and hi, move low after mid
            else return mid;                        //The middle number is the number we look for
        }
        return -1;
    }
}

And here's some python:

def binarySearch(key, a):
    ## assume that the array is already sorted
    lo = 0
    hi = len(a) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2  ##postion mid, integer division
        if key < a[mid]:
            hi = mid - 1           ##key is between mid and low, move hi before mid
        elif key > a[mid]:
            lo = mid + 1           ##key is between mid and hi, move lo after mid
        else:
            return mid             ##mid is where our number resides
    return -1                      ##number is not found


print binarySearch(2, [0, 1, 2, 3, 4, 5, 6, 7]) ##just a test

Read More