Lesson 7.6

Binary search

Part 7: AlgorithmsReading, about 8 min2 exercises in this lesson

Java answers can't run on ExamSpine yet. You can still read Java, trace it, and put an answer's lines in order.

Binary search

By the end of this you will be able to write a binary search in Python and in Java, explain why it only works on sorted data, and say why it is so much faster than a linear search.

How it is asked

Binary search is the other search the course names. There are no past papers for the new course yet. Expect to write it, as a function or method that returns an index or -1, as for linear search, plus two new shapes:

Explain why it needs the data to be sorted. This asks for a reason, so a good answer links the order to throwing half away, rather than just saying "sorted".
Compare it with a linear search: its Big O, and when you would still pick the linear one.

Tracing it and counting its comparisons gets its own lesson, next.

Key idea: Each comparison throws away half of what is left, so a binary search on n sorted values is O(log n).

Watch it halve

Think of guessing a number between 1 and 100 when you are told "higher" or "lower" after each guess. You would start at 50, not at 1. A binary search does that to a sorted list. It keeps two indexes, low and high, around the part that could still hold the target, and looks at the middle.

Step through it

values = [3, 8, 12, 17, 21, 26, 30, 34, 41]

target = 34

low = 0

high = len(values) - 1

position = -1

while low <= high and position == -1:

mid = (low + high) // 2

if values[mid] == target:

position = mid

elif values[mid] < target:

low = mid + 1

else:

high = mid - 1

print(position)

Variables

Nothing yet. Press Next to run the first line.

Nothing has run yet.

Output

(nothing printed)

0/21

Watch low jump: 21 is too small, so the left half goes; 30 is too small, so more goes; then 34.

The search looked at 21, then 30, then 34. A linear search would have looked at eight values to reach 34.

Why it needs sorted data

Throwing half the list away is only safe because of the order. When the middle value is 21 and the target is 34, every value to the left of 21 is smaller than 21, so none of them can be 34. Here is the same search, for the same target, on the same nine values in a jumbled order.

Step through it

values = [26, 3, 41, 17, 12, 34, 8, 30, 21]

target = 34

low = 0

high = len(values) - 1

position = -1

while low <= high and position == -1:

mid = (low + high) // 2

if values[mid] == target:

position = mid

elif values[mid] < target:

low = mid + 1

else:

high = mid - 1

print(position)

Variables

Nothing yet. Press Next to run the first line.

Nothing has run yet.

Output

(nothing printed)

0/27

Unsorted data: the search throws away the part it should have kept, and reports -1 for a value that is there.

The program did not crash, and it did not warn anyone. It just gave a wrong answer. That is why the data must be sorted before a binary search, and why a question that asks why wants the reason, not just the rule.

Quick check

Why does a binary search need the list to be sorted?

As a function

As a function, a return replaces the position variable.

def binary_search(values, target):
    low = 0
    high = len(values) - 1
    while low <= high:
        mid = (low + high) // 2
        if values[mid] == target:
            return mid
        elif values[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1


print(binary_search([3, 8, 12, 17, 21], 17))
print(binary_search([3, 8, 12, 17, 21], 5))

public static int binarySearch(int[] values,
                               int target) {
    int low = 0;
    int high = values.length - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (values[mid] == target) {
            return mid;
        } else if (values[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

public static void main(String[] args) {
    int[] values = {3, 8, 12, 17, 21};
    System.out.println(
        binarySearch(values, 17));
    System.out.println(
        binarySearch(values, 5));
}

Both print 3, then -1. Three details in these few lines are where most wrong versions go wrong.

The loop runs while low <= high, not low < high. When low equals high, one value is still left to check.
low moves to mid + 1 and high to mid - 1, past the middle. The middle has just been checked, and moving past it makes the range shrink on every turn, so the loop always ends.
In Python the middle is (low + high) // 2. A single / gives a decimal such as 3.0, which cannot be used as an index. In Java, / on two ints already throws the remainder away.

Quick check

A student writes while low < high:. For the list [4, 9] and target 9, what happens?

How it is marked

An exam-style question of our own, with a mark for each part of the algorithm. The second script has the two slips above.

How it is marked

The array values is sorted in ascending order. Construct a function that uses a binary search to return the index of target in values, or -1 if it is not there. [5]

[5]

low = 0 and high = len(values) - 1[1]
The range starts as the whole list.

So far 1 of 5

Three of five: each slip is one character, and each costs a mark.

How fast it is

Each turn throws away the middle value and one of the halves. So 1000 values leave at most 500 after one look, then 250, 125, 62, 31, 15, 7, 3, 1 and none: at most 10 looks. A million values need at most 20. That is O(log n). A linear search on a million values could need a million looks.

Quick check

A sorted list doubles from 1000 values to 2000. In the worst case, what happens to the number of looks a binary search makes?

When linear search still wins

Binary search needs the list sorted first, and sorting takes far more work than one linear search. So:

To search an unsorted list once, a linear search is the better choice: O(n), and no sorting.
To search the same list many times, sort it once, then each binary search is O(log n).
A list that is small, or always changing, is often fine with a linear search.

Now try it yourself on the questions below.

Exercise 7.6.17.6.1 · Write itBinary search

Write a function that does a binary search for target in a list (an array in Java) of whole numbers.

The list is sorted from smallest to largest, and no value appears twice.
Return the index of target, or -1 if it is not in the list.
The list can be empty.

Use a binary search: keep a low and a high index, look at the middle value between them, and throw away the half that cannot hold the target. Do not use a ready-made search. Only the value your function returns is checked.

def binary_search(values: list[int], target: int) -> int

You cannot use these in this question:

.index()
import bisect
import operator

This question is about writing the binary search yourself, so ready-made searches are not allowed.

Examples

Your function is tested on 12 cases: the 3 examples below, and 9 hidden ones that check the rules above.

binary_search([2, 5, 8, 12, 16, 23, 38, 56, 72, 91], 23) should return 5: found after a few halvings (rule 2)
binary_search([2, 5, 8, 12, 16, 23, 38, 56, 72, 91], 7) should return -1: not in the list (rule 2)
binary_search([4, 9], 9) should return 1: the last value of two: low and high meet on it (rule 2)

public static int binarySearch(int[] values, int target)

Running Java here comes later. You can put this answer's lines in order instead. You can still write your Java answer (it stays while this page is open) and compare it with our worked solution. Or try this exercise in Python.Checking whether Java answers can run here.

You cannot use these in this question:

Arrays.binarySearch()
Collections.binarySearch()
.indexOf()

This question is about writing the binary search yourself, so ready-made searches are not allowed.

Examples

Your function is tested on 12 cases: the 3 examples below, and 9 hidden ones that check the rules above.

binarySearch(new int[]{2, 5, 8, 12, 16, 23, 38, 56, 72, 91}, 23) should return 5: found after a few halvings (rule 2)
binarySearch(new int[]{2, 5, 8, 12, 16, 23, 38, 56, 72, 91}, 7) should return -1: not in the list (rule 2)
binarySearch(new int[]{4, 9}, 9) should return 1: the last value of two: low and high meet on it (rule 2)

solution.pySolution.java

def binary_search(values: list[int], target: int) -> int:
    # your code here
    pass

Exercise 7.6.27.6.2 · Write itWhere binary search looks

A binary search looks at only a few values of a sorted list. Write a function that does a binary search for target in a list (an array in Java) of whole numbers, and returns the indexes it looked at, in the order it looked at them.

The list is sorted from smallest to largest, and no value appears twice.
Start with low at the first index and high at the last. While low is not past high, look at the middle index mid, which is low + high divided by 2, rounded down. Add mid to the list you return.
If the value at mid is the target, stop. If it is smaller than the target, move low to mid + 1. If it is bigger, move high to mid - 1.
If the target is not in the list, the search stops when low passes high. Return the indexes it looked at before that.
An empty list is looked at nowhere, so return an empty list.

In Java, return an ArrayList<Integer>; ArrayList is already imported for you. Only the value your function returns is checked.

def binary_search_probes(values: list[int], target: int) -> list[int]

Examples

Your function is tested on 11 cases: the 3 examples below, and 8 hidden ones that check the rules above.

binary_search_probes([3, 8, 12, 17, 21, 26, 30, 34, 41], 34) should return [4, 6, 7]: found on the third look (rules 2 and 3)
binary_search_probes([3, 8, 12, 17, 21, 26, 30, 34, 41], 21) should return [4]: the middle value is the target (rule 3)
binary_search_probes([3, 8, 12, 17, 21, 26, 30, 34, 41], 5) should return [4, 1, 0]: not there: three looks, then low passes high (rule 4)

public static ArrayList<Integer> binarySearchProbes(int[] values, int target)

Examples

Your function is tested on 11 cases: the 3 examples below, and 8 hidden ones that check the rules above.

binarySearchProbes(new int[]{3, 8, 12, 17, 21, 26, 30, 34, 41}, 34) should return [4, 6, 7]: found on the third look (rules 2 and 3)
binarySearchProbes(new int[]{3, 8, 12, 17, 21, 26, 30, 34, 41}, 21) should return [4]: the middle value is the target (rule 3)
binarySearchProbes(new int[]{3, 8, 12, 17, 21, 26, 30, 34, 41}, 5) should return [4, 1, 0]: not there: three looks, then low passes high (rule 4)

solution.pySolution.java

def binary_search_probes(values: list[int], target: int) -> list[int]:
    # your code here
    pass

Report a problem with this page