Binary Search

The binary search method works with a data set that has been sorted into ascending or descending order and employs the method of chopping the list into smaller and smaller pieces until the item is found. Given the list of numbers above we must sort them into order:

 11 12 14 15 23 36 54 76 83 98

Given the requirement to find item 76 we proceed as follows:

• Find the mid point of the list and determine whether the item there is the one we require.
• If item is found the search can stop, otherwise we need to know whether the item found is greater than or smaller than the item being sought:
• If the item at the mid point is greater than the one sought then we discard that part of the list which is greater than the mid-point and concentrate on the sub_list of items that are less than the mid-point;
• if the item at the mid-point is less than the one we seek then we discard the smaller values to the left and concentrate on the larger values to the right.

Here is a simple form that allows the user to enter a number to search for in the data set; the second edit box states whether or not the item was found:

The code for the Search button is as follows:

procedure TForm1.Button1Click(Sender: TObject);
var
 left, right, mid :integer;
 found:Boolean;
begin
 left := 1;
 right := max;
 found:=false;
 while (left <= right) and (not found) do
 begin
  mid:=(right+left) div 2;  //integer division
  if numlist[mid] = strtoint(edit1.Text) then
  found := true
  else
  if  strtoint(edit1.Text) >  numlist[mid] then
   left:=mid+1  //eliminate lower range of values
  else
  if  strtoint(edit1.Text) < numlist[mid] then
   right:=mid-1;  //eliminate upper range of values
 end;
 if found then edit2.text := edit1.Text + ' found'
 else
  edit2.text := edit1.Text + ' not found';
 edit1.Clear;
 edit1.SetFocus;
end;

Explanation

The algorithm requires three integer variables to track the progress of the search:

• left to hold the lower array index
• right to hold the upper array index
• mid to hold the index accessed at each stage of the search.

The left index starts at 1 while the right index starts at the maximum index of the array (10 in this case)

Inside a while loop the value of mid is calculated from (left + right) div 2. If left = 1 and right = 10 then mid = 11 div 2 = 5 - this is the first cell to search for the value required.

If the item required is in the cell indexed by mid then the search is over.

If the item required is greater than the item indexed by mid then the left index is changed to the position of mid + 1. This removes the lower part of the list from further searching because the item cannot lie in this part.

If the item required is less than the item indexed by mid then the right index is changed to the position of mid - 1. This removes the upper part of the list from further searching because the item cannot lie in this part.

The conditions for continuing the while loop are that found should be false and also that the left index should not cross over the right index, in which case the item required will not be in the list.

Test Run

If the target is 54 the values of mid, left and right go through this sequence:

mid = (10+1) div 2 = 5;  numlist[5]= 23, < 54 so left becomes mid + 1 = 6
mid = (6+10) div 2 = 8;  numlist[8]=76, > 54 so right becomes mid - 1 = 7
mid = (6+7) div 2 = 6;  numlist[6]=36, < 54 so left becomes mid + 1 = 7
mid = (7+7) div 2 = 7;  numlist[7]=54, the target item.

If the target is 5 the values of mid, left and right go through this sequence:

mid = (1+10) div 2 = 5;  numlist[5]= 23, > 5 so right becomes mid - 1 = 4
mid = (1+4) div 2 = 2;  numlist[2]=12, > 5 so right becomes mid - 1 = 1
mid = (1+1) div 2 = 1;  numlist[1]=11, > 5 so right becomes mid - 1 = 0
the while loop now stops because the condition left < right is no longer met.

For a binary search the maximum number of cycles required to find items will be int(log₂ n) + 1; for 10 this will be 4 because int(log₂ n) = 3, + 1 = 4 (2^4=16, the next power of 2 above 10). You could also find the nearest power of two greater than the value: 16 = 2^4. Can you find an item in the list above that takes 5 cycles? Modify the program by adding a cycles variable, increment inside the while loop and output its value in the second edit box. Can you get a value greater than int(log₂ n) + 1? You could try increasing the size of the array to between 16 and 31 to check that this gave a value of 5. Increasing the size of the array above this would be time-consuming but might prove the point beyond all doubt.

Back