Binary Search

A binary search searches according to an algorithm which allows it to find a record with less attempts on the average than a linear search. Essentially a binary search looks at the middle element and then determines whether the match you are searching for is above or below this essentially eliminates half of the table in the first search. It then looks at the middle of the next half etc. Obviously for a binary search to work, the table has to be sorted/sequenced by the element you are searching on.

In this example, I am using a table with elements running from 501 to 600 (100 elements in the table) and I want to find **562**. The steps involved are:

**Step 1:** Move the size of the table + 1 to the upper limit field (100 + 1 = 101)

**Step 2:** Move 0 to the lower limit field

**Step 3: ** Compute the subscript using the formula (upper limit + lower limit) / 2. For example for the first search it would be (101 + 0) / 2 = 50 (note that truncation was used). The subscript points to the element in the table to be compared to 562. Using my example, for the first search the number in the 50^{th} element, which is 550, is compared to 562.

**Step 4: ** Compare the subscript to the lower limit field to see if the search is complete. In the first search, that means comparing 50 to 0. If the two fields are equal, the desired item is in error because it is not in the table and the search is done.

**Step 5: ** Ask the question: is the item from the table that the subscript is pointing to equal to the desired item in this case 562. On the first search, this would not be true since 550 does not equal 562.

**Step 6: ** If they are equal, the item has been found and the appropriate processing should be done. At this point, the search is over since the desired item has been found.

**Step 7: ** Ask the question: is the item from the table less than the desired item. For this first search, this means is 550 less than 562.

**Step 8: ** If it is, move the subscript value to the lower limit field. For the first search, this means that 50 is moved to the lower limit. At this point another pass is started beginning with step 3.

**Step 9: ** If the item from the table is neither less than or equal to the desired item than the item from the table must be greater than the desired item. In this case, move the subscript to the upper limit and start another pass through the search beginning with step 3.

501 |
502 |
550 |
562 |
575 |
600 |
|||||||||

1 |
2 |
50 |
62 |
75 |
100 |

Calculations:

(101 + 0) / 2 = 50 in subscript |

550 < 562 therefore 50 moved to lower limit (101 + 50) / 2 = 75 in subscript |

575 > 562 therefore 75 moved to upper limit (75 + 50) / 2 = 62 in subscript |

562 = 562 therefore the item is found and the search terminates |