Further algorithms - EdexcelBinary search

A binary search is an efficient method of searching an ordered list. It will not work on a list that has not been sorted first.

A written description of a binary search algorithm is:

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 and a message is sent.
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 two to four continue until a match is made or there are no more items to be found and a message is sent.

Consider this list of ordered numbers:

Consider searching 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. An alternative is to round down, but be 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 pseudo-code might look like this:

SET find TO 11 SET found TO False SET length TO LENGTH(list) SET lowerBound TO 0 SET upperBound TO length WHILE found = False DO midpoint = (upperBound + lowerBound) DIV 2 IF list[midPoint] = find THEN SEND 'Found at' & midpoint TO DISPLAY SET found TO True ELSE IF list[midPoint]> item THEN SET upperBound TO midpoint - 1 ELSE SET lowerBound TO midpoint + 1 END IF END IF END WHILE IF found = False THEN SEND 'Not found' TO DISPLAY END IF

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 7 steps.

However, a binary search can only work if a list has been sorted into order.