Faster binary search to find the index in Python?

Question

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.

Could anyone please help? Thanks in advance.

Answer 1

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