Lesson 7.6 · Write it
Binary search
A functionPython or Java12 tests, 9 of them hidden
On a phone? Put the lines in order instead
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-1if 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)