# Faster binary search to find the index in Python?

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[0] or x > a[-1]:
return -1
elif x == a[0]:
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.

I can see the problem with your code. Why This "mid = right // 2 " ?

You can try below code

def binarySearch(arr, low, high, key):
if high >= low:
mid = (high + low) // 2
if arr[mid] == key:
return mid
elif arr[mid] > key:
return binarySearch(arr, low, mid - 1, key)
else:
return binarySearch(arr, mid + 1, high, key)
else:
return -1
• It's because left is always 0, actually. Jun 23, 2020 at 22:34
• @Lnz sublist ooeration in python is not $O(1) \ it \ is \ O(n)$ and you are doing sub list in each iteration, this is the reason of slowness . Jun 24, 2020 at 4:43
• stackoverflow.com/questions/39338520/… Jun 24, 2020 at 4:44
• I read this and find that you are right. But the first two lines are in the question. Jun 25, 2020 at 0:56
• I think you are right. I can call your function in that function. Jun 26, 2020 at 5:29