Write it

Find a book

A functionPython or Java12 tests, 8 of them hidden

On a phone? Put the lines in order instead

A school library gives every book a whole-number ID. The IDs are kept in a list (an array in Java) called ids, sorted from smallest to largest, with no ID appearing twice.

Write a function that uses a binary search to return the position (the index) of target in ids, or -1 if no book has that ID. Positions start at 0.

Keep two positions, low and high, for the part of the list that could still hold target. They start at the first and the last position.
Look at the middle position, (low + high) divided by 2, rounded down. If the ID there is target, return that position. If it is smaller than target, search only the part after it; if it is larger, search only the part before it.
When low has passed high, nothing is left to search, so return -1.
ids can be empty, and holds at most 10000 IDs, each between 1 and 1000000.
Write the search yourself. The shortcuts listed with this question are not allowed.

The tests check only the number your function returns, so they cannot tell a binary search from a linear one. In the exam, a linear search would not earn the marks for this part.

def find_book(ids: list[int], target: int) -> int

You cannot use these in this question:

.index()
.count()
.find()
import bisect

A Paper 2 question that asks for a binary search wants to see the search written out, so the built-in searches are not allowed.

Examples

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

find_book([104, 117, 123, 138, 150, 162, 171], 150) should return 4: 150 is found on the third look, at position 4
find_book([104, 117, 123, 138, 150, 162, 171], 138) should return 3: 138 is the first middle looked at
find_book([104, 117, 123, 138, 150, 162, 171], 140) should return -1: no book has ID 140 (rule 3)
find_book([205], 205) should return 0: one book, and it is the one wanted: low and high are equal and still need checking (rule 3)

public static int findBook(int[] ids, 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()
Arrays.asList()
.binarySearch()
.indexOf()
.contains()
.stream()
import java.util.stream

A Paper 2 question that asks for a binary search wants to see the search written out, so the built-in searches are not allowed.

Examples

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

findBook(new int[]{104, 117, 123, 138, 150, 162, 171}, 150) should return 4: 150 is found on the third look, at position 4
findBook(new int[]{104, 117, 123, 138, 150, 162, 171}, 138) should return 3: 138 is the first middle looked at
findBook(new int[]{104, 117, 123, 138, 150, 162, 171}, 140) should return -1: no book has ID 140 (rule 3)
findBook(new int[]{205}, 205) should return 0: one book, and it is the one wanted: low and high are equal and still need checking (rule 3)

solution.pySolution.java

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