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 Answer 1

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

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.