Binary Search Implementation Using Slicing

Question

Regarding the binary search implementation given below:

def bin_search(arr, key):
    n = len(arr)
    if n < 2:
       return (0 if (n == 1 and arr[0] == key) else None)
    m = int(0.5 * n)
    if arr[m] > key:
       return bin_search(arr[:m], key)
    result = bin_search(arr[m:], key)
    return (result + m if result != None else None)  

For the above binary search implementation, time complexity will be affected as we are taking slice of an array and space complexity too as list slicing in python creates a new list object. For improving the above implementation, I am thinking of introducing lower and upper bound variables just as in its original implementation. But it will modify the above code implementation completely.

Can you please let me know how to modify the above implementation so that the time and space complexity of it is improved and is my understanding regarding its complexity correct?

Answer 1

Here is iterative solution with time complexity of O(log(n)) and space complexity of O(1). Instead of modifying array you just modify the positions of pointers. I mean left/right by pointers.

def binary_search(array, target):
    return binary_search_helper(array, target, 0, len(array) - 1)


def binary_search_helper(array, target, left, right):
    while left <= right:
        middle = (left + right) // 2
        match = array[middle]

        if target == match:
            return middle
        elif target < match:
            right = middle - 1
        else:
            left = middle + 1

    return -1

Recursive solution: I don't see a way to improve complexity with a slight changes since you need to work with positions instead of array itself. That will affect your base case and function calls. Here is my attempt to reduce space complexity from O(n) to O(log(n)).

def bin_search(arr, key, left=0, right=len(arr) - 1):
    # Should change base case since we modify only pointers
    if left > right:
        return None

    # since we are not modifying our array working with length will not work
    m = int(0.5 * (left + right))

    if arr[m] == key:
        return m
    elif arr[m] > key:
       return bin_search(arr, key, left, m - 1)
    else:
        return bin_search(arr, key, m + 1, right)

PS: Need to create arr beforehand or create another caller function since we define right=len(arr) - 1 in function definition. I would recommend using caller function like this:

def binary_search_caller(arr, key):
    return bin_search(arr, key, 0, len(array) - 1)

And change function definition to:

def bin_search(arr, key, left, right):
    ...