Binary Search

The binary search is a particularly efficient way of searching a large linear list, if the data is in order.  The binary search is also known as the binary chop because it employs a ‘divide and conquer’ strategy.

Binary search algorithm

Suppose we are searching for a target value of 63.

First we identify the middle of the list and compare the value at this position with the target value.

binary_search1

If the value in the middle of the list is not equal to the target value, we ask if the target is larger or smaller than the value in the middle.  If the target is larger than the middle value, we discard the lower half of the list.  So this is our new list.

binary_search2

Now we do the same again, identify the middle of the list and compare the value at this position with the target value.

binary_search3

If the value in the middle of the list is not equal to the target value, we ask if the target is larger or smaller than the value in the middle.  If the target is larger than the middle value, we discard the lower half of the list.  So this is our new list.

binary_search4

Now we do the same again, identify the middle of the list and compare the value at this position with the target value.

binary_search5

If the value in the middle of the list is not equal to the target value, we ask if the target is larger or smaller than the value in the middle.  This time, the target is smaller than the middle value, so we discard the upper half of the list.  So this is our new list.

binary_search5-5

Now we do the same again, identify the middle of the list and compare the value at this position with the target value.  In this case there are only 2 items left, either one of them can be considered as the middle of the list.  One way or the other, you can see we will eventually find the target value, or not.

binary_search6

Binary search pseudocode

iLow = LBound(DataArray)
iHigh = UBound(DataArray)

Do While iLow <= iHigh
    iMiddle = (iLow + iHigh) / 2
    If Target = DataArray(iMiddle) Then
            bFound = True
            Exit Do
    ElseIf Target < DataArray(iMiddle) Then
            iHigh = (iMiddle – 1)
    Else
            iLow = (iMiddle + 1)
    End If
Loop

Summary

  • The Binary Search, otherwise known as the Binary Chop, is a ‘divide and conquer’ algorithm
  • The data must be in order to begin with
  • Doubling the amount of data has little impact on performance
  • Very efficient with large, sorted, data sets