I am implementing a binary search algorithm and my code is as shown bellow:
def binary_search(a, x): left, right = 0, len(a) if right == 0: return -1 if x < a or x > a[-1]: return -1 elif x == a: return 0 elif x == a[-1]: return right - 1 mid = right // 2 a_mid = a[mid] if x == a_mid: return mid elif x < a_mid: return binary_search(a[left:mid], x) elif x > a_mid: idx = binary_search(a[mid+1:right], x) if idx == -1: return -1 else: return mid + 1 + idx
I tested it and cannot find any way to improve it by complexity. Someone suggested that I may "have used an incorrect base condition to terminate your loop" but I still cannot figure out where the problem lies.
Could anyone please help? Thanks in advance.