Know Your Binary Search

Chris wrote a binary search program that returns the index of the number \(x\) in list \(L\), \(-1\) if not found.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def search(x,L):
    lo = 0
    hi = len(L)
    while lo < hi:
        mid = (lo + hi) / 2
        if L[mid] == x:
            return mid
        elif L[mid] < x:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Weird enough, when he runs search(6,L) on the list L = [1,2,3,4,5,6,7,8] the code returns -1 instead of 5. Which is the only line Chris should edit to correct the code?

×

Problem Loading...

Note Loading...

Set Loading...