����ý

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.