Binary Search Output giving wrong answer-CodePudding

This is my code:

def binary_search(keys, query):
    low, high = 0, 0
    while low <= high:
        midpoint = low   (high - low) // 2
        if query == keys[midpoint]:
            return midpoint
        elif keys[midpoint] > query:
            high = midpoint - 1 
        else:
            low = midpoint   1
    return -1       
           

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 am inputting:

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

I should be getting this as output:

2 0 -1 0 -1

but I am getting this instead:

-1 0 -1 0 -1

CodePudding user response：

You are starting with both low and high equal to 0, which doesn't make sense. Change the first two lines to the following:

low, high = 0, len(keys)
while low < high:

CodePudding user response：

Consider what happens when you're looking for 8 in 1 5 8 12 13.

low and high start out as 0 and 0, respectively. midpoint therefore is 0.

keys[midpoint] is 1.

This is less than query, which is 8. Thus low is set to 1. low is now greater than high so the loop ends, and the function returns -1.