1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ It's because left is always 0, actually. \$\endgroup\$ – Lnz Jun 23 '20 at 22:34
  • 1
    \$\begingroup\$ @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 . \$\endgroup\$ – Lakshman Jun 24 '20 at 4:43
  • \$\begingroup\$ stackoverflow.com/questions/39338520/… \$\endgroup\$ – Lakshman Jun 24 '20 at 4:44
  • \$\begingroup\$ I read this and find that you are right. But the first two lines are in the question. \$\endgroup\$ – Lnz Jun 25 '20 at 0:56
  • \$\begingroup\$ I think you are right. I can call your function in that function. \$\endgroup\$ – Lnz Jun 26 '20 at 5:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.