Recursive binary search not working systematically

Question

I am implementing the binary search algorithm with both an iterative and recursive approach.

The first line of the input contains an integer n and a sequence of n pairwise distinct positive integers in increasing order. The next line contains an integer k and k positive integers.

For all i from 0 to k - 1, output an index 0 <= j <= n-1 such that a_j = b_i, or -1 if there is no such index. (for each algorithm implementation)

a and b are respectively the elements of each sequence.

Input:

5 1 5 8 12 13
5 8 1 23 1 11

Output:

2 0 -1 0 -1
2 0 -1 0 -1
2 0 -1 0 -1

I managed to implement the iterative, recursive version and a linear search version.

import sys

def binary_search_it(a, x):
    left, right = 0, len(a) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if x == a[mid]:
            return mid
        # left--mid--x--right
        if a[mid] < x:
            left = mid + 1
        # left--x--mid--right
        elif x < a[mid]:
            right = mid - 1
    return - 1

def binary_search_rec(a, x):
    left, right = 0, len(a) - 1
    if right < left:
        return left - 1
    mid = left + (right - left) // 2
    if x == a[mid]:
        return mid
    if x < a[mid]:
        return binary_search_rec(a[: mid - 1], x)
    else:
        return binary_search_rec(a[mid + 1:],x)


def linear_search(a, x):
    for i in range(len(a)):
        if a[i] == x:
            return i
    return -1

if __name__ == '__main__':
    input = sys.stdin.read()
    data = list(map(int, input.split()))
    n = data[0]
    m = data[n + 1]
    a = data[1 : n + 1]
    for x in data[n + 2:]:
        # replace with the call to binary_search when implemented
        print(binary_search_it(a, x), end=' ')
    print('\n')
    for x in data[n + 2:]:
        print(linear_search(a, x), end=' ')
    print('\n')
    for x in data[n + 2:]:
        print(binary_search_rec(a, x), end = ' ')

So far everything is fine, for the example above the code return the same output for all three implementations.

If I try to use another sample dataset I have an issue in my recursive approach

Input:

5 1 2 3 4 5
5 1 2 3 4 5

Output (expected):

0 1 2 3 4
0 1 2 3 4
0 -1 2 0 0

Can someone explain me the flow in my code and how you manage to identify the problem?

score 2 · Accepted Answer · answered Jan 05 '19 at 13:44

There are multiple problems with this implementation:

Using slicing is expensive and makes this algorithm O(n)
The recursive algorithm never ever returns -1 to indicate that the item was not found.

A recursive implementation of binary search still needs to track left and right to be O(log n).

def binary_search_rec(a, x):
    return _binary_search(a, x, 0, len(a) - 1)

def _binary_search(a, x, left, right):
    if right < left:
        return -1

    mid = (right + left) // 2
    if x == a[mid]:
        return mid
    if x < a[mid]:
        return _binary_search(a, x, left, right - 1)
    else:
        return _binary_search(a, x, left + 1, right)

score 1 · Answer 2 · answered Jan 05 '19 at 13:36

The problem is this line:

...
if x < a[mid]:
    return binary_search_rec(a[: mid - 1], x)  <---
...

The upperbound on a slice is exclusive. See for e.g. this question for more details.

How to find such problems? Either by knowing the algorithm and the language well enough to identify mistakes in the code by reading it, or via a debugger. A debugger should come with every IDE available for python, or standalone. Learning to use one should be one of the top-priorities of any beginning coder.

Recursive binary search not working systematically

2 Answers2