Know Your Binary Search

Computer Science Level 3

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

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?

Line 3 : hi = len(L)-1 Line 4 : while lo <= hi: Line 9 : lo = mid Line 11 : hi = mid None of these choices

1 solution

Christopher Boo
Jun 23, 2016

In terms of definition of search range, there are two types of implementation for the Binary Search algorithm.

Type 1 : $(l,r)$ implies the range $[l,r] = \{l,l+1,\dots ,r-2,r-1,r\}$

Applying this definition, line $3$ is wrong because L[hi] does not exist. Line $4$ is also incorrect because it terminates when lo == hi but in this case the search space is not empty. We have to change $2$ lines to make this implementation work.

Type 2 : $(l,r)$ implies the range $[l,r) = \{l,l+1,\dots ,r-2,r-1\}$

Using this definition, hi is one right to the rightmost possible number. Line $3$ makes sense as L[len(L)-1] is the rightmost number. Line $4$ is also true because when lo == hi this implies that the search space is empty. The only line that contains error is in line $11$ which happens when L[mid] > x . In this case, mid-1 is still a possible number to be $x$ but not mid . Hence, hi should be mid instead of mid-1 .

Know Your Binary Search

1 solution

0 pending reports