Lesson 7.6 · Write it

Where binary search looks

A functionPython or Java11 tests, 8 of them hidden

On a phone? Put the lines in order instead

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)

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.

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