91�ȱ�

A binary search is an efficient method of searching an ordered list.

A binary search works like this:

1. Start by setting the counter to the middle position in the list.
2. If the value held there is a match, the search ends.
3. If the value at the midpoint is less than the value to be found, the list is divided in half. The lower half of the list is ignored and the search keeps to the upper half of the list.
4. Otherwise, if the value at the midpoint is greater than the value to be found, the upper half of the list is ignored and the search keeps to the lower half of the list.
5. The search moves to the midpoint of the remaining items. Steps 2 through 4 continue until a match is made or there are no more items to be found.

Consider this list of ordered numbers:

Suppose we were to search for the value 11.

The midpoint is found by adding the lowest position to the highest position and dividing by 2.

Highest position (8) + lowest position (0) = 8

8/2 = 4

NOTE - if the answer is a decimal, round up. For example, 3.5 becomes 4. We can round down as an alternative, as long as we are consistent.

Check at position 4, which has the value 7.

7 is less than 11, so the bottom half of the list (including the midpoint) is discarded.

The new lowest position is 5.

Highest position (8) + lowest position (5) = 13

13/2 = 6.5, which rounds up to 7

Check at position 7, which has the value 14.

14 is greater than 11, so the top half of the list (including the midpoint) is discarded.

The new highest position is 6.

Highest position (6) + lowest position (5) = 11

11/2 = 5.5, which rounds up to 6

Check at position 6.

The value held at position 6 is 11, a match. The search ends.

A binary search in pseudocode might look like this:

find = 11
found = False
length = list.length
lowerBound = 0
upperBound = length
            
while (lowerBound <= upperBound) 
     midpoint = int((upperBound + lowerBound))/2
     if list[midPoint] == find then
          print('Found at' , midpoint)
          found = True
     endif
     if list[midpoint]> find then
          upperBound = midpoint-1
     else
          lowerBound = midpoint+1
     endif
endwhile            

if found == False then
     print('Not found')
endif

A binary search is a much more efficient algorithm than a linear search. In an ordered list of every number from 0 to 100, a linear search would take 99 steps to find the value 99. A binary search would only require seven steps.

However, a binary search can only work if a list is ordered.