Binary Search with Duplicates producing wrong result at unknown key and list

Question

I am trying to solve a Binary Search problem, where the output is the location of the first appearance of the key in a sorted list.

I have managed to solve the first part, where I find any location where the key appears in the sorted list by using Binary Search. But the second part, where its first appearance is found, is going wrong for an unknown key and sorted list.

The code for binary search with duplicates:

import math
import random

def binary_search(keys, query):
    low = 0
    high = len(keys) - 1


    def searchdef(keys, query, low, high):
        if low > high:
            return -1, 0, 0
        x = math.floor(low + (high-low)/2)
        if query != keys[x]:
            if query > keys[x]:
                for i in range(0, len(keys)-1):
                    return searchdef(keys, query, x+1, high)
            if query < keys[x]:
                return searchdef(keys, query, low, x-1)
        else:
            return x, high, low

    def finddup2(x, low):
        z = x-1
        while query == keys[z] and z != -1:
            return min(z, finddup2(z, low))
        else: return x
    
        

    x, high, low = searchdef(keys, query, low, high)
    ans = finddup2(x, low)
    return ans     



if __name__ == '__main__':
    
    num_keys = int(input())
    input_keys = list(map(int, input().split()))
    assert len(input_keys) == num_keys

    num_queries = int(input())
    input_queries = list(map(int, input().split()))
    assert len(input_queries) == num_queries

    for q in input_queries:
        print(binary_search(input_keys, q), end=' ')

I have tried to stress test the code by using a linear search, but after many checks it produces a recursion error.

Stress Test Code:

import math
import random

def binary_search(keys, query):
    low = 0
    high = len(keys) - 1


    def searchdef(keys, query, low, high):
        if low > high:
            return -1, 0, 0
        x = math.floor(low + (high-low)/2)
        if query != keys[x]:
            if query > keys[x]:
                for i in range(0, len(keys)-1):
                    return searchdef(keys, query, x+1, high)
            if query < keys[x]:
                return searchdef(keys, query, low, x-1)
        else:
            return x, high, low

    
    def finddup2(x, low):
        z = x-1
        while query == keys[z] and z != -1:
            return min(z, finddup2(z-1, low))
        else: return x
    
        

    x, high, low = searchdef(keys, query, low, high)
    ans = finddup2(x, low)
    return ans     


def search(arr, N, x):
 
    for i in range(0, N):
        if (arr[i] == x):
            return i
    return -1

if __name__ == '__main__':

    def random_no():
        num_keys = int(50)
        input_keys = random.sample(range(1, 100), 50)
        input_keys.sort()
        assert len(input_keys) == num_keys

        num_queries = int(1)
        input_queries = [random.choice(input_keys)]
        assert len(input_queries) == num_queries
        return input_keys, input_queries

    input_keys, input_queries = random_no()

    def check(input_keys, input_queries):
        for q in input_queries:
            a = binary_search(input_keys, q)
            b = search(input_keys, len(input_keys), q)
            print(a, end=' ')
            print(b, end=' ')
            while a == b:
                print(a, end=' ')
                print(b, end=' ')
                print("ok")
                input_keys, input_queries = random_no()
                check(input_keys, input_queries)
            else:
                print(input_keys)
                print(q)
                print(a, end=' ')
                print(b, end=' ')               
                print("wrong")
                
    

    check(input_keys, input_queries)

Error I'm getting:

RecursionError: maximum recursion depth exceeded in comparison

I would like to know what has gone wrong with my code, and why the stress test is also not working.

Edit:

My new code after some changes:

import math
import random

def binary_search(keys, query):
    low = 0
    high = len(keys) - 1


    def searchdef(keys, query, low, high):
        if low > high:
            return -1, high, low
        x = math.floor(low + (high-low)/2)
        if query != keys[x]:
            if query > keys[x]:
                return searchdef(keys, query, x+1, high)
            if query < keys[x]:
                return searchdef(keys, query, low, x-1)
        else:
            return x, high, low
    
    def finddup2(x, low):
        z = x-1
        if query == keys[z] and z != -1:
            return min(z, finddup2(z, low))
        else: return x
    
        

    x, high, low = searchdef(keys, query, low, high)
    ans = finddup2(x, low)
    return ans     



if __name__ == '__main__':
    
    num_keys = int(input())
    input_keys = list(map(int, input().split()))
    assert len(input_keys) == num_keys

    num_queries = int(input())
    input_queries = list(map(int, input().split()))
    assert len(input_queries) == num_queries

    for q in input_queries:
        print(binary_search(input_keys, q), end=' ')

It still returns a wrong answer after black box testing. My stress test cannot find what the value causing the wrong answer is. Could you please help me?

Edit 2: I came up with a slight change. Now, the code is returning the correct answer, but is exceeding the time limit. I request help.

import math

def binary_search(keys, query):
    low = 0
    high = len(keys) - 1


    def searchdef(keys, query, low, high):
        if low > high:
            return -1
        if query < keys[low]:
            return -1
        if query > keys[high]:
            return -1
        if low <= high :
            x = math.floor(low + (high-low)/2)
            if query == keys[x]:
                while query == keys[x-1] and x != 0:
                    x -=1
                return x
            if query > keys[x]:
                return searchdef(keys, query, x+1, high)
            if query < keys[x]:
                return searchdef(keys, query, low, x-1)    
        

    x = searchdef(keys, query, low, high)
    return x



if __name__ == '__main__':
    
    num_keys = int(input())
    input_keys = list(map(int, input().split()))
    assert len(input_keys) == num_keys

    num_queries = int(input())
    input_queries = list(map(int, input().split()))
    assert len(input_queries) == num_queries

    for q in input_queries:
        print(binary_search(input_keys, q), end=' ')

First the case `low == high` should be treated as a stopping criterion. Second the line ` for i in range(0, len(keys)-1):` is a mistake. — Remi Cuingnet, Jan 18 '23 at 08:40
I have removed the line `for i ... -1) `. I don't know how that got in there. Also, is this what you meant by the stopping criterion: `if low == high: if query == keys[0]: return 0, high, low else: return -1, high, low ` — Akaren, Jan 18 '23 at 09:02
my mistake. The second problem seems to come from the line `check(input_keys, input_queries)` that should not exist — Remi Cuingnet, Jan 18 '23 at 09:22
https://stackoverflow.com/questions/39416560/how-can-i-simplify-this-working-binary-search-code-in-c/39417165#39417165 — Matt Timmermans, Jan 18 '23 at 17:22

trincot · Accepted Answer · 2023-01-18T17:06:45.460

The problem with the binary search is that return min(z, finddup2(z-1, low)) skips an index: z is already one less than the current index, so you should not subtract 1 from it again. It should be return min(z, finddup2(z, low))

Secondly, when the value is not found, and x == -1, the function finddup2 should not be called. So:

    x, high, low = searchdef(keys, query, low, high)
    if x == -1:
        return -1
    ans = finddup2(x, low)
    return ans

There are many other comments to make, like why you have a while loop that returns in its first iteration. It should just be an if. Also a for loop has a return in its first iteration, so that loop should not be there at all. Making finddup2 recursive is not a good idea as this may use a lot of stack space. Make it iterative.

The problem with the stress test code is that it is calling itself recursively and causes a stack overflow.

Here is proposed correction of your testing code:

    def random_no(num_keys=50, num_queries=10):
        input_keys = random.sample(range(1, 100), num_keys)
        input_keys.sort()
        input_queries = random.choices(input_keys, k=num_queries)
        return input_keys, input_queries

    def check(input_keys, input_queries):
        for q in input_queries:
            a = binary_search(input_keys, q)
            b = search(input_keys, len(input_keys), q)
            if a != b:
                print(input_keys)
                print(q)
                print(a, b, "wrong")
                raise ValueError("wrong result")
    

    for _ in range(100):
        input_keys, input_queries = random_no()
        check(input_keys, input_queries)

    print("all done")

Time efficiency

The function finddup2 is inefficient, both in terms of space (stack) and time. In the worst case it would have to scan half of the input list, which makes it O() and kills the advantage you would have from the binary search algorithm, which has a time complexity of O(log). But O(log) + O() = O(), so it has degraded to the performance of a linear search.

Also using math to convert a floating point number to integer is worse than just using the integer division operator (//).

To make this efficient, you should make sure that the binary search algorithm continues to drill down the tree until it is certain to have found the leftmost occurrence of a number.

Here is an adaptation of your binary_search that doesn't need finddup2. Note that you don't need to pass keys and query as arguments to your inner function, as it has access to those names anyhow:

def binary_search(keys, query):
    low = 0
    high = len(keys) - 1

    def searchdef(low, high):
        if low > high:
            if low >= len(keys) or keys[low] != query:
                return -1
            return low
        x = (low + high) // 2
        if query > keys[x]: 
            return searchdef(x + 1, high)
        else:  # Continue also when equal!
            return searchdef(low, x - 1)
            
    return searchdef(low, high)

Thank you. I've made the changes you suggested. The stress test finally works now. Yet the black box testing unit I ran it through still states that my result is wrong for some value after about 20 tests. I've added my new code in an edit above. Could you please help me with what it could be? — Akaren, Jan 18 '23 at 10:34
Does it say the answer is wrong, or that it took too much time? What are the constraints of the input? Can you link to the challenge? — trincot, Jan 18 '23 at 11:18
'Failed case #22/57: Wrong answer (Time used: 0.02/5.00, memory used: 41586688/536870912.) ` is the output. So the answer is wrong. Time used is pretty less. The input is a natural number. I can't seem to be able to link to it. — Akaren, Jan 18 '23 at 11:57
I can see a problem when the query value is not in the list. See second paragraph I added to the answer. — trincot, Jan 18 '23 at 12:13
That helped! I managed to shift some code, and figured out a different way to do things. The code is exceeding the time limit now, though. Can you please help? `Failed case #54/57: time limit exceeded (Time used: 10.00/5.00, memory used: 41664512/536870912.) ` — Akaren, Jan 18 '23 at 16:46
Yes, I expected that, since `findup2` is doing a linear search which is inefficient. See addition to answer. — trincot, Jan 18 '23 at 17:07

Binary Search with Duplicates producing wrong result at unknown key and list

1 Answers1

Time efficiency