def binarysearch(alist,item):
    first = 0
    last = len(alist) -1
    found = False

    while first< last and not found:
        mid = (first + last) //2
        if alist[mid] == item:
            found = True
        elif alist[mid] < item:
            first = mid + 1
        else:
            last = mid - 1
    return found

边界问题？ mid = len//2 , 9//2 ==4 10//2 = 5 ,new 边界[mid-1] or [mid+1]

When we split the list enough times, we end up with a list that has just one item. Either that is the item we are looking for or it is not. Either way, we are done. The number of comparisons necessary to get to this point is_i_wheren2i=1n2i=1. Solving for_i_gives usi=logni=log⁡n. The maximum number of comparisons is logarithmic with respect to the number of items in the list. Therefore, the binary search is O(logn)

Before we move on to the analysis, we should note that this algorithm is a great example of a divide and conquer strategy. Divide and conquer means that we divide the problem into smaller pieces, solve the smaller pieces in some way, and then reassemble the whole problem to get the result

def binarysearch(alist,item):
    if len(alist) == 0:
        retrun False
    mid = len(alist)//2
    if alist[mid] == item:
        return True
    elif (alist[mid] > item):
        return binarysearch(alist[:mid],item)
    else:
        return binarysearch(alist[mid+1:],item)

Q-14: Suppose you have the following sorted list

and are using the recursive binary search algorithm. Which group of numbers correctly shows the sequence of comparisons used to search for the key 16?

target = 16 ,len = 10 mid[5] = 12, 10//2 = 5

[1,15,17,18] mid[2] = 17

[1,15] mid[1] = 15

12, 17, 15

target = 3, mid = list[4] = 13, 9//2 = 4, half list = [0,1,2,8]

[0,1,2,8]

mid[2] = 2

[8]