Binary Search

The binary search is also known as the binary chop, as the data set is cut into two halves for each step of the process. It is a very much faster search method than linear search, but to be effective the data set must be in sorted order in the array. If the data set changes rapidly and requires regular re-sorting then this will offset the speed gain offered by binary search over linear search.

To perform binary search, three index variables are required. By tradition these are called ‘top’, ‘middle’ and ‘bottom’. Top is initialised to one end of the array, often 0, and bottom is set to indicate the other end of the array. Once these two variables are set, the value of middle can be computed. Middle is set to the midway value between top and bottom. The value indexed by middle is compared with the target value. There are initially three possible outcomes that we have to consider:

  1. The value indexed by middle matches the target. In this case the search has found the target and the function can return a value indicating that the search has succeeded.
  2. The value is higher than the middle value in which case only the values from middle to end need to be searched
  3. The value is lower than the middle value in which case the search is carried out between zero and the middle value.

To illustrate this process, consider the following scenario – the data in the array is sorted and the target is 29. We start by setting top to 9, bottom to 0, and calculating middle to be (0 + 9) / 2. This rounds down to 4 using  integer arithmetic, so middle is set to 4.

ADS 03 C

From this we can conclude that the target value is in the lower half of the table. This means that top must be set to middle and a new value of middle calculated. In this case the value of middle will be (4 + 0)/2 which C will deliver as 2. The contents of array element 2 matches the target, so in this case the search is successfully concluded.

A couple of practical issues present themselves at this point:

  • If top == bottom then the search has concluded. Unless the value at middle (and middle must be the same as top and bottom) is the target, then the search has determined that the target is not in the data set.
  • Unless some care is taken then the search may end in a loop with top equal to (bottom + 1). There are circumstances where this loop does not terminate.

Next: Sorting Algorithms