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.