Binary Search

If our data is presorted then a binary search starts to make a lot of sense. It is like the guessing game we mentioned earlier where you need to find a number between 1 and 100. No one asks for 1 then 2 then 3… until they find it.

Instead we ask for the mid point, and then find out if we are higher or lower, and with each pass we eliminate 50% of the remaining elements.

This is the same idea for a binary search. Search a sorted list, and you can move there faster by eliminating 50% of the remaining elements until you find you actual item.

This is relatively fast to code, especially if you are using recursion. Here is an example of some pseudo-code.

Function FindElement(Array, SearchItem, Low, High)
   Index = Int((Low + High) / 2)
      If Array[index] == SearchItem Then
         Return SearchItem
      Else
          If Array[Index] < SearchItem Then
             FindElement(Array, SearchItem, Low, Index)
          Else
             FindElement(Array, SearchItem, Index, High)
          End If
      End If
End Function

Binary Search was originally found on Access 2 Learn