Time Limit Exceeded for Binary Search in Python-CodePudding

I have created a binary search program in python but I am getting "time limit exceeded" for one of the test cases. Any idea how I can optimize my code to reduce the running time?

My code basically finds the index of the median term and compares the query to the integer at the median. I then update the array to either the left half (if the query is less than the median) or the right half (if the query is more than the median).

If the query is equal to the median, then the index is returned.

If the length of the array is 1 and the query is not equal to the sole integer in the array, -1 is returned. Otherwise the index of the sole integer in the array is returned.

Below is my code.

Thanks everyone for your help!

def binary_search(keys, query):
    array_to_search = keys
    
    while len(array_to_search) > 1:
        median = len(array_to_search) // 2
        if q < array_to_search[median]:
            # split list from starting point up to median index
            array_to_search = array_to_search[:median]
            continue
        elif q > array_to_search[median]:
            # split list from median index up to last index
            array_to_search = array_to_search[median:]
            continue
        else:
            return keys.index(array_to_search[median])
    
    if q == array_to_search[0]:
        return keys.index(array_to_search[0])
    else:
        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=' ')

CodePudding user response：

Your algorithm was in an infinite loop, hence the "time limit exceeded" error.

With the caveat that there are definitely more efficient ways to implement binary search, I think your logic can be adjusted to make a working version as follows:

#def binary_search(keys, query): # used different argument name 'query' from the name 'q' used in the function body
def binary_search(keys, q):
    array_to_search = keys
    
    i = 0 # we need to track changes to the start of the array
    while len(array_to_search) > 1:
        median = len(array_to_search) // 2
        if q < array_to_search[median]:
            # split list from starting point up to median index
            array_to_search = array_to_search[:median]
            continue
        elif q > array_to_search[median]:
            # split list from median index up to last index
            #array_to_search = array_to_search[median:] # median has already been checked, so we can start at median   1 instead
            array_to_search = array_to_search[median   1:]
            i  = median   1 # we need to track changes to the start of the array
            continue
        else:
            return i   median # return value needs to reflect changes to the start of the array
    
    #if q == array_to_search[0]: # we need to check that the array is not empty
    if array_to_search and q == array_to_search[0]:
        return i # return value needs to reflect changes to the start of the array
    else:
        return -1

def foo():
    '''
    #I have eliminated the input logic for testing purposes
    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
    '''

    # here is an arbitrary test case
    input_keys = [0,2,4,6,8,10,12,14,16,18,20]
    input_queries = [0,6,12,18,20,-1,9,21]

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

foo()

Output:

0 3 6 9 10 -1 -1 -1

Regarding efficiency improvements, note that slicing operations such as array_to_search[:median] and array_to_search[median 1:] will make copies which will take something like n/2 time for the first one, then n/4 for the second, then n/8 etc, adding O(n) time complexity to binary search, an algorithm that could otherwise be O(log n). This is why it is often implemented instead using two pointers (such as left and right) to track the ever-shrinking subarray within which the search is being conducted. You may want to take a look at Wikipedia for an example of this.