Why is the counter not increasing in this binary search code in python?

Question

def binary_search(array,key,left,right):
    if left>right:
        return -1
    mid=(right+left)//2

    if key==array[mid]:
        return mid
    i=0
    if key<array[mid]:
        i+=1
        print("subarray at step {} : {}".format(i,array[left:mid]))
        return binary_search(array,key,left,mid-1)

    elif key>array[mid]:
        i+=1
        print("subarray at step {} : {}".format(i,array[mid:right]))
        return binary_search(array,key,mid+1,right)



array=[1,2,3,4,5,6,7,8,9,11,22,33,44,55,66,77,88,99,222,333]
res= binary_search(array,88,0,len(array))

print(res if res!=-1 else "Not found")

In this binary search code, I couldn't figure out why the counter wan not working. Each time the i is printed a 1. The counter doesn't increase. What am I doing wrong? Thank you.

If you are using an IDE now is a good time to learn its debugging features - like setting breakpoints and examining values. Or you could spend a little time and get familiar with the built-in Python debugger. Also, printing stuff at strategic points in your program can help you trace what is or isn't happening. — wwii
– wwii, Commented Oct 4, 2020 at 18:00
You're calling the search function recursively. For each call, only a section of the full array is passed. i always starts as 0 for the section. — Mike67
– Mike67, Commented Oct 4, 2020 at 18:01
@wwii I tried using the debugger in pycharm a few times. But I couldn't figure out how. Do you have any blogs or youtube vidoes I could refer to learn debugger. — Nithin Gowda
– Nithin Gowda, Commented Oct 4, 2020 at 18:13

Aniket Singla · Accepted Answer · 2020-10-06 13:53:35Z

1

i is being printed as 1 because you are i is being set to 0 inside binary_search function on each call. try moving out initiaization of i outside the function.


def binary_search(array,key,left,right):
    global i
    if left>right:
        return -1
    mid=(right+left)//2

    if key==array[mid]:
        return mid
    # i=0
    if key<array[mid]:
        i+=1
        print("subarray at step {} : {}".format(i,array[left:mid]))
        return binary_search(array,key,left,mid-1)

    elif key>array[mid]:
        i+=1
        print("subarray at step {} : {}".format(i,array[mid:right]))
        return binary_search(array,key,mid+1,right)


i =0
array=[1,2,3,4,5,6,7,8,9,11,22,33,44,55,66,77,88,99,222,333]
res= binary_search(array,88,0,len(array))

You need to change the scope of variable i to make it global.

edited Oct 6, 2020 at 13:53

answered Oct 4, 2020 at 18:09

Aniket Singla

6051 gold badge8 silver badges23 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

KayseMca · Accepted Answer · 2020-10-04 18:17:02Z

0

make i as global variable and to assing valuable call global keywoard

i = 0
def binary_search(array,key,left,right):
    if left>right:
        return -1
    mid=(right+left)//2
    # i=0

    if key==array[mid]:
        return f'it found position {mid}'
    
    if key<array[mid]:
        global i 
        i = i+1
        print("subarray at step {} : {}".format(i,array[left:mid]))
        return binary_search(array,key,left,mid-1)

    elif key>array[mid]:
        i+=1
        print("subarray at step {} : {}".format(i,array[mid:right]))
        return binary_search(array,key,mid+1,right)



array=[1,2,3,4,5,6,7,8,9,11,22,33,44,55,66,77,88,99,222,333]
res= binary_search(array,88,0,len(array))
print(len(array))

print(res if res!=-1 else "Not found")

answered Oct 4, 2020 at 18:17

KayseMca

401 silver badge6 bronze badges

2 Comments

Nithin Gowda Over a year ago

Shouldn't you have to give global while declaring the variable? This code works. Like global i i=0

KayseMca Over a year ago

no you dont check the third if I call there the global keywoard global i otherwise you will get an error

Collectives™ on Stack Overflow

Why is the counter not increasing in this binary search code in python?

2 Answers 2

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related