1

I am trying to count the number of searches being performed with binary search.

def binarySearch(l, value, low = 0, high = -1):
    if not l:
        return -1
    if(high == -1):
        high = len(l)-1
    if low == high:
        if l[low] == value:
            return low
        else:
            return -1
    mid = (low+high)//2
    if l[mid] > value:
        return binarySearch(l, value, low, mid-1)
    elif l[mid] < value:
        return binarySearch(l, value, mid+1, high)
    else:
        return mid

I had a friend suggest using a for loop and counting the number of iterations, but therein lies my confusion. I am uncertain of the parameters by which to initialize the for loop to perform said task.

Any thoughts would be greatly appreciated. Thanks.

Shannon
  • 119
  • 1
  • 1
  • 10

1 Answers1

3

you can have counter variable

def binarySearch(l, value, low = 0, high = -1):
    binarySearch.counter += 1

you can initialize it with zero before calling the function

binarySearch.counter =0
l=[1,4,5,6]
binarySearch(l,1,0,-1)
print binarySearch.counter
radar
  • 13,270
  • 2
  • 25
  • 33
  • Thank you, I will try implementing this. I am new to python syntax and was not aware a variable could be defined this way. – Shannon Oct 18 '14 at 04:08
  • @Shannon : `binarySearch.counter` is a function attribute. It's a cute trick for a situation like this, but it does have its pitfalls. See [Python function attributes - uses and abuses](http://stackoverflow.com/questions/338101/python-function-attributes-uses-and-abuses) for further info. – PM 2Ring Oct 18 '14 at 05:41
  • @PM2Ring Thank you very much for the additional information. – Shannon Oct 18 '14 at 05:44