Sorting, searching and validation - EduqasBinary search

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 are repeated until a match is made or there are no more items to be searched.

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

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 remaining 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 as integer found as Boolean lowerBound as integer upperBound as integer midPoint as integer list[8] set find = 11 set found = FALSE set lowerBound = 0 set upperBound = len(list) while found = FALSE set midPoint = (upperBound + lowerBound)DIV 2 if list[midPoint] = find output “Found at ”&midPoint set found = TRUE else if list[midPoint] > find set upperBound = midPoint-1 else set lowerBound = midPoint+1 end if end if end while if found = FALSE output “Not found” 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 require only seven steps.

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