Now that we have learnt binary search, it’s time to implement it. You can work in any programming language of your choice - Python, C++, Java, or anything else you want. Let’s get started!

Implementing Binary Search

Implement binary_search(array, element), which returns the first position at which element is found in array. Note that the array elements and not necessarily unique. It is guaranteed that element can be found in array.

Python

Below, we provide a short Python code template:

# binary_search.py
def binary_search(array, element):
    # do stuff

C++, Java, etc

If you’re not using Python, have your implementation accept test cases from standard input, and print results to standard output.

Input description: The first line contains the number of test cases T. Each test case is described in 3 lines. The first line has 2 numbers, the size of the array N and the number of queries Q. The second line has N numbers in non-decreasing order, the array to be searched. The third line has Q numbers, where each number is the target to search for in the array.

Sample input:

2
3 2
1 2 4
2 1
6 5
2 3 12 14 19 24
12 19 12 19 2

Output description: Output should contain T lines. Each line should contain the answers for the queries for the respective test case. That is, for each target, the 0-indexed position in the array at which the target can be found.

Sample output:

1 0
2 4 2 4 0

Notes

The trickiest part about implementing binary search is making sure there are no edge cases when calculating high, low, mid. It’s a good idea to create test cases of all sizes from one power of two to another (say 4 through 8). Common mistakes include (a) infinite loops when array size is 2, and (b) out-of-index errors when the answer is the first or last element of the array.

Grading your solution

Python

You can use the following file to grade your solution.

# grader.py 
from __future__ import print_function
import bisect
import datetime
import random
from binary_search import binary_search
npassed, nfailed = 0, 0
for itest in range(1, 13):
    print('Test case:', itest)
    # number of elements in array
    nelements = random.randint(int(10**(itest/2.))/2, int(10**(itest/2.)))
    print('Array size:', nelements)
    # create array
    array = list()
    for ii in range(nelements):
        element = random.randint(0, 10) + (array[-1] if array else 0)
        array.append(element)
    # nqueries
    nqueries = random.randint(4*nelements/5, nelements)
    # accumulate total number correct and time taken
    total_time = 0.0
    correct = list()
    for iquery in range(nqueries):
      # generate query
        element = array[random.randint(0, len(array)-1)]
        # output and answer
        tic = datetime.datetime.now()
        output = binary_search(array, element)
        toc = datetime.datetime.now()
        answer = bisect.bisect(array, element) - 1
        # check
        correct.append(answer == output)
        total_time += (toc-tic).total_seconds()
    # print results
    if all(correct):
        print('PASSED (Runtime = %.2f seconds)' % total_time)
        npassed += 1
    else:
        print('FAILED')
        nfailed += 1
    print('='*100)
print('TOTAL PASSED: %d. TOTAL FAILED: %d.' % (npassed, nfailed))

C++, Java, etc

You’ll find all the files required to check your solution here: Binary Search. In particular, the folder includes 3 files - input, answer and grader.py.

Do the following to check your solution.

{COMMAND TO RUN C++/JAVA CODE} < input > output 
python grader.py output answer

Solution

The solution for this assignment can be found here: binary_search.py. The code takes about 4 seconds to run for 800,000 queries on an array of size 1,000,000. Note that if you implemented the solution in C++ / Java, your code should be executing about > 5x faster.

If we used naive search, solving the above task would take about 10 days.