Study Guide

Binary Search

How to find an item in a sorted list by checking the middle and throwing away half each time, traced step by step, written in pseudocode, and compared with a linear search by counting the checks each needs.

Lesson 5.17 Algorithms and Programming

For: Key Stage 3 learners (about ages 12 to 14) who have met loops, arrays and a linear search, and Cambridge IGCSE Computer Science learners wanting a second searching algorithm

Stage: Think

Guess the number

Two friends play a guessing game. One thinks of a whole number from 1 to 100. The other guesses, and after every guess the first friend says only “higher”, “lower” or “correct”. The game is fictional, but you may have played something like it.

Think it through

What number would you guess first, and why? Roughly how many guesses do you think you would need, at most, to be sure of getting the answer?

Show a model answer

A good first guess is 50. Whatever the answer, “higher” or “lower” rules out half of the numbers at once: after guessing 50, either 1 to 50 or 51 to 100 is gone. Guessing 1 first would only rule out one number if it were wrong. Repeating the idea, the numbers left go from 100 to about 50, 25, 12, 6, 3 and 1, so seven guesses are always enough. You will see why in this lesson.

Stage: Discover

Throwing away half the list

A fictional school has 15 lockers, and a sorted list records the locker numbers in use, from smallest to largest. The list is stored in an array called Lockers.

Positions 1 to 15 hold these numbers, in order: 3, 8, 12, 17, 21, 26, 30, 35, 41, 47, 52, 58, 63, 70, 77. So position 1 holds 3, position 8 holds 35, position 10 holds 47 and position 15 holds 77.

The caretaker wants to know whether locker number 47 is in use. A linear search would start at position 1 and read on.

Think it through

Using what you noticed in the guessing game, which position would you look at first to find 47 in this list? What would the number there tell you about where 47 could be?

Show a model answer

Position 8, which holds 35, has seven items before it and seven after it. Since 35 is smaller than 47 and the list is sorted from smallest to largest, every item at positions 1 to 8 is 35 or smaller, so 47 cannot be there. Only positions 9 to 15 are still possible: one check has thrown away more than half the list.

Checking the middle item, and using the answer to throw away the half that cannot hold the target, then repeating on the half that is left, is a binary search. The “binary” refers to the two halves: at every check there are two ways to go, up or down. Each check leaves at most half of the items still in play, so the list shrinks very quickly.

Check your understanding

The search for locker 47 checks the middle item, 35, in the sorted list above. What can the search now ignore?
Show the answer

Answer: B. Locker 35 and every locker before it, because 47 is bigger than 35.

When the middle item is smaller than the target, the target can only be in the items after the middle one; when it is bigger, only in the items before it.

Stage: Predict

Why the list must be in order

Now imagine that the locker list was not in order, and the caretaker looked at the middle item and found 35 again. The list begins 52, 3, 70, 17, 35, …

Think it through

Does knowing that the middle item is 35, which is smaller than 47, tell you anything about where 47 might be? Explain.

Show a model answer

No. With no order, 47 could be anywhere: before the 35 or after it. The middle item being smaller than 47 says nothing about the other items, so no part of the list can be thrown away. The “higher or lower” answer only helps when the list is in order.

Check your understanding

Why can a binary search only be used on a sorted list?
Show the answer

Answer: C. The “bigger” or “smaller” answer only shows which half to keep in a sorted list.

The sorted order is what makes “throw away half” safe. A binary search on a list that is not sorted can miss an item that is really there.

Stage: Explain

Keeping track: Low, High and Mid

A program cannot look at a list the way a person does. It needs to remember which part of the list is still possible. It does this with two position numbers, Low (the first position still possible) and High (the last position still possible), and finds the middle position, Mid, between them:

Mid ← DIV(Low + High, 2)

DIV gives the whole-number part of a division and drops the remainder (Lesson 9). The first time, Low is 1 and High is 15, so Mid is DIV(16, 2), which is 8.

The target is 47. Low is 1, High is 15, so Mid is 8, and Lockers[8] is 35.

  1. Compare the middle item with the target. 35 is smaller than 47.
  2. Decide which part can be thrown away. The target is bigger than the middle item, so it can only be after position 8. Positions 1 to 8 are no longer possible.
  3. Move Low just past the middle. Low becomes 9, which is Mid + 1. Writing Low ← Mid would keep position 8 in play, even though it has been checked.
  4. If the middle item were bigger than the target, the target could only be before it, and High would become Mid - 1, for the same reason.
  5. If the middle item equals the target, the search has found it and stops.

The next Mid is DIV(9 + 15, 2), which is 12.

Check your understanding

In another search, Low is 1 and High is 8. What is Mid, using DIV(Low + High, 2)?
Show the answer

Answer: A. 4, because DIV(9, 2) gives the whole-number part of 4.5.

A search always has a whole-number Mid, so it can read Lockers[Mid].

Stage: Explain

The whole algorithm

Here is the whole search in Cambridge pseudocode. The array Lockers has already been filled with the fifteen numbers above, in order, so Lockers[1] is 3 and Lockers[15] is 77. The loop keeps going while the target has not been found and at least one position is still possible (Low <= High).

INPUT Target
Low ← 1
High ← 15
Found ← FALSE
WHILE Found = FALSE AND Low <= High DO
  Mid ← DIV(Low + High, 2)
  IF Lockers[Mid] = Target
    THEN
      Found ← TRUE
    ELSE
      IF Lockers[Mid] < Target
        THEN
          Low ← Mid + 1
        ELSE
          High ← Mid - 1
      ENDIF
  ENDIF
ENDWHILE
IF Found = TRUE
  THEN
    OUTPUT Target, " is at position ", Mid
  ELSE
    OUTPUT Target, " is not on the list"
ENDIF

When the target is found, the loop stops straight away, so Mid still holds the position where it was found.

Follow the search for locker 47, one pass of the loop at a time.

Searching for 47 in the sorted locker list

Each step is one pass of the loop: find Mid, check the item there, then move Low or High, or stop.

  1. Pass 1

    Step 1 of 3: Low 1, High 15, Mid 8

    Mid is DIV(16, 2) = 8. Lockers[8] is 35, which is smaller than 47, so Low becomes 9.

    Technical detail: Positions 1 to 8 are thrown away. Seven positions, 9 to 15, are left.

  2. Pass 2

    Step 2 of 3: Low 9, High 15, Mid 12

    Mid is DIV(24, 2) = 12. Lockers[12] is 58, which is bigger than 47, so High becomes 11.

    Technical detail: Positions 12 to 15 are thrown away. Only 9, 10 and 11 are left.

  3. Pass 3

    Step 3 of 3: Low 9, High 11, Mid 10

    Mid is DIV(20, 2) = 10. Lockers[10] is 47, which equals the target, so Found becomes TRUE and the loop stops.

    Technical detail: The program outputs “47 is at position 10”. Only three items were looked at; a linear search would have looked at ten.

Check your understanding

In pass 2 of the search for 47, Lockers[12] is 58. Why does High become 11, and not stay at 15 or become 12?
Show the answer

Answer: B. Because 58 is bigger than 47, so 47 can only be before position 12.

When the middle item is too big, High moves to just before it: High ← Mid - 1.

Stage: Experiment

Trace it yourself

Fill in the trace table for the search for 47. The first row is given. Use the steps above to check yourself afterwards, not before.

A binary search for 47 in the locker list
PassLowHighMidLockers[Mid]Lockers[Mid] compared with 47
1115835smaller
215
3

    Show the completed table
    PassLowHighMidLockers[Mid]Lockers[Mid] compared with 47
    1115835smaller
    29151258bigger
    39111047equal

    Three passes. The search stopped as soon as the item was found.

    Now a harder trace, with no worked help after the first row. The caretaker asks for locker 50, which is not on the list. Work out what the search does, and when it decides to stop.

    A binary search for 50, which is not in the list
    PassLowHighMidLockers[Mid]Lockers[Mid] compared with 50
    1115835smaller
    215
    3
    4
    End1110--Low is now bigger than High

      Show the completed table
      PassLowHighMidLockers[Mid]Lockers[Mid] compared with 50
      1115835smaller
      29151258bigger
      39111047smaller
      411111152bigger
      End1110--Low is now bigger than High

      Four items were looked at. After pass 4, Low (11) is bigger than High (10): no position is left, so the loop ends and the program outputs “50 is not on the list”.

      Check your understanding

      In the search for 50, why does the loop end after pass 4 when no item equalled 50?
      Show the answer

      Answer: D. Because Low is bigger than High, so there are no positions left that could hold 50.

      A search that has ruled out every position stops and says “not found”. That is why the condition needs Low <= High as well as Found = FALSE.

      Stage: Discover

      How many checks, at most?

      Every check throws away at least half of the positions that are left. That gives a way to count the most checks a search could need.

      Think it through

      A sorted list has 15 items. After the first check of the middle item, at most how many items can still be the answer? After the second check? After the third? What does that tell you about the most checks needed for 15 items?

      Show a model answer

      The middle item is checked, and 14 items are left in two halves of 7. After the first check at most 7 are still possible; after the second at most 3; after the third at most 1; and the fourth check looks at that last one. So at most 4 checks are needed for 15 items.

      Working backwards gives the largest sorted list that can be searched with a given number of checks. One check handles one item. Each extra check adds a new middle item and doubles the part either side of it: two halves of the previous size, plus one.

      The largest sorted list that a binary search can finish within a number of checks
      Checks allowedLargest list that can be searched
      11
      23
      3
      4
      5
      6
      7

        Show the completed table
        Checks allowedLargest list that can be searched
        11
        23
        37
        415
        531
        663
        7127

        Each extra check roughly doubles the size of list that can be searched.

        Check your understanding

        A sorted list has 1000 items. Using the pattern in the table (7 checks cover 127 items, and each check doubles and adds 1), what is the most checks a binary search needs?
        Show the answer

        Answer: B. 10, because 10 checks cover 1023 items, but 9 checks cover only 511.

        Doubling the size of the list adds only one more check. That is why a binary search stays fast on very long lists.

        Stage: Explain

        Comparing two algorithms

        For 100 items, 7 checks cover 127 items but 6 cover only 63, so a binary search needs at most 7 checks. A linear search might need up to 100. Here is the comparison, counting one check each time the program looks at an item in the list:

        Items in the sorted listLinear search, at mostBinary search, at most
        15154
        1001007
        1000100010
        1 000 0001 000 00020

        Comparing algorithms for the same problem means choosing a fair measure, here the most items looked at, and reasoning from it. “Which is quicker?” has no single answer: it depends on what is known about the list.

        Do not confuse: Linear search and binary search

        Does the list need to be sorted?Linear search
        No. It works on any list, because it only compares with each item in turn.A club list in the order the pupils joined.
        Does the list need to be sorted?Binary search
        Yes. Throwing away half the list is only safe when the list is in order.The locker list, smallest to largest.
        How many checks for 100 items, at most?Linear search
        Up to 100, one for each item.
        How many checks for 100 items, at most?Binary search
        At most 7, because each check halves what is left.

        A binary search is not simply better: it needs the order, and a list that is not sorted must be sorted first.

        “The middle” means the middle position, not the middle value. In a sorted list that begins 1, 2, 3, 100, 200, the middle item of the five is the third one, 3, even though 100 is nearer to the halfway point between 1 and 200. A binary search never looks at the values to decide where the middle is; it only uses DIV(Low + High, 2).

        Also, a binary search is not always quicker. If the target happens to be the middle item, one check finds it, but if the target is the first item of a long list, a linear search finds it with one check, whereas a binary search needs several.

        Apply it

        A fictional school office keeps its 600 pupil numbers sorted, and checks one number each morning. A technician says: “A binary search will always beat a linear search, because it looks at fewer items.” Which reply is most accurate?
        Show the answer

        Answer: B. Mostly correct: about 10 checks at most for 600 items, but a linear search can win on an early target.

        Compare algorithms on the same measure and the same cases: the worst case shows that a binary search scales much better, even though a particular target can favour a linear search.

        Stage: Apply

        Spot the mistake

        Sam (fictional) rewrites the update lines of the binary search like this. Everything else is the same.

        IF Lockers[Mid] < Target
          THEN
            Low ← Mid
          ELSE
            High ← Mid - 1
        ENDIF

        Apply it

        A sorted list has two items, 10 and 20, in positions 1 and 2, and the target is 20. Low is 1, High is 2, Mid is DIV(3, 2) = 1, and Lockers[1] is 10. What happens with Sam’s update?
        Show the answer

        Answer: A. Low becomes 1 again, so Mid stays 1, and the loop repeats for ever.

        The new Low or High must move past the item that has just been checked. If it does not, the search can look at the same item for ever.

        Priya (fictional) runs the locker search on a list that nobody has sorted: 40, 10, 30, 20, 50, in positions 1 to 5, for the target 20.

        Apply it

        Low starts at 1 and High at 5. What does the program output, and what does this show?
        Show the answer

        Answer: A. “20 is not on the list”, even though 20 is there, because the order broke the search.

        A binary search on an unsorted list can throw away the very half that holds the target, and then report that it is not there.

        Stage: Apply

        Counting the checks in code

        Think it through

        Change the pseudocode of the whole algorithm so that it also counts how many items the search looks at, and outputs that number at the end. Then say what it would output for the target 47 in the locker list, and for 50.

        Show a model answer
        INPUT Target
        Low ← 1
        High ← 15
        Found ← FALSE
        Checked ← 0
        WHILE Found = FALSE AND Low <= High DO
          Mid ← DIV(Low + High, 2)
          Checked ← Checked + 1
          IF Lockers[Mid] = Target
            THEN
              Found ← TRUE
            ELSE
              IF Lockers[Mid] < Target
                THEN
                  Low ← Mid + 1
                ELSE
                  High ← Mid - 1
              ENDIF
          ENDIF
        ENDWHILE
        IF Found = TRUE
          THEN
            OUTPUT Target, " is at position ", Mid
          ELSE
            OUTPUT Target, " is not on the list"
        ENDIF
        OUTPUT "Items looked at: ", Checked

        Checked starts at 0 and goes up by 1 on each pass, straight after Mid is worked out. For 47 the loop runs three times, so it outputs 47 is at position 10 and Items looked at: 3. For 50 it runs four times, so it outputs 50 is not on the list and Items looked at: 4, as the two traces showed.

        Go deeper The same binary search in Python
        lockers = [3, 8, 12, 17, 21, 26, 30, 35, 41, 47, 52, 58, 63, 70, 77]
        target = 47
        low = 0
        high = len(lockers) - 1
        found = False
        checked = 0
        while not found and low <= high:
            mid = (low + high) // 2
            checked = checked + 1
            if lockers[mid] == target:
                found = True
            elif lockers[mid] < target:
                low = mid + 1
            else:
                high = mid - 1
        if found:
            print(target, "is at position", mid + 1)
        else:
            print(target, "is not on the list")
        print("Items looked at:", checked)
        • Python counts positions from 0, so low starts at 0 and high at len(lockers) - 1; the position is shown as mid + 1 to match the pseudocode. // is Python’s DIV. Lesson 18 introduces the language.
        • This program prints 47 is at position 10 and Items looked at: 3. Changing target to 50 prints 50 is not on the list and Items looked at: 4.
        • Python also has built-in ways to search, such as the bisect module. Writing the algorithm out shows what they do.

        Stage: Consolidate

        Show what you know

        Think it through

        Explain to a friend how a binary search finds an item in a sorted list, and why it is so much quicker than a linear search on a long list. Use the guessing game or a list of your own.

        Show a model answer

        A good answer says that a binary search checks the middle item, uses the fact that the list is sorted to decide which half the target can be in, throws the other half away, and repeats on what is left until it finds the item or nothing is left. Each check halves the list, so doubling the length of the list adds only one more check: 100 items need at most 7, where a linear search might need 100. It only works because the list is in order.

        Apply it

        A fictional shop keeps 10 000 product codes in order from smallest to largest, and its tills look up a code hundreds of times a day. The list changes once a week. Which search should the tills use, and why?
        Show the answer

        Answer: C. A binary search, because the list stays sorted, so each look-up needs only a few checks.

        When a list is already sorted and searched often, a binary search wins. If a list is searched once and is not sorted, putting it in order first may cost more than a linear search.

        Think it through

        Which part of this lesson are you least sure about? Write one question you would ask your teacher.

        Show a model answer

        There is no wrong answer. Two questions worth asking: “how do I decide whether to use Mid - 1 or Mid + 1?” (move past the item just checked) and “what if the list has an even number of items?” (DIV still gives a whole number, so the search still works).

        • A binary search finds an item in a sorted list by checking the middle item, throwing away the half that cannot hold the target, and repeating on the half that is left.
        • The middle position is Mid ← DIV(Low + High, 2). If Lockers[Mid] is smaller than the target, Low ← Mid + 1; if bigger, High ← Mid - 1; if equal, the item is found. The loop ends when it is found or when Low becomes bigger than High.
        • A list of 100 items needs at most 7 checks, 1000 items at most 10, and a million at most 20: each doubling of the list adds one check. A linear search might need to look at every item.
        • The list must be in order. On an unsorted list a binary search can discard the half that holds the target and report that it is missing.
        • Usual faults: Low ← Mid instead of Mid + 1, a loop that never ends, thinking “middle” means middle value, and using the search on an unsorted list.

        Sources and scope

        • What this lesson is. The seventeenth lesson of the Algorithms and Programming module, written for this site. It teaches binary search, the second searching algorithm after Lesson 11, and compares the two by counting checks. Its curriculum links are provisional and imply no review or endorsement by any examination board, and they were written against the published Key Stage 3 programme of study, Cambridge IGCSE Computer Science 0478 and Cambridge International AS & A Level Computer Science 9618.
        • Original material. The guessing game, the school lockers, the pupil numbers, the shop and Sam and Priya are fictional, written for this lesson. Every trace was worked out by hand and checked with an equivalent Python program, which also confirmed the greatest number of items looked at for a list of 15, 100 and 1000 items.
        • Simplified on purpose. The comparison counts only the items a program looks at, and ignores the other work in the loop. Lists are short, numeric and have no repeated items. The lesson does not name Big O notation or the cost formula; it shows the doubling pattern only. A binary search for the first of several equal items, and searching with recursion, are not taught.
        • Left to later lessons. Sorting other than bubble sort (Lesson 11), and measuring how fast an algorithm grows in general.