二分查找

面试官:会二分查找吗?来,写一下

def binary_search(alist,num):
    n = len(alist)
    
    if len(alist) == 0:
        return False
    mid = n // 2
    
    if alist[mid] == num:
        return True
    elif alist[mid] < num:
        return binary_search(alist[mid+1:],num)
    else: 
        return binary_search(alist[0:mid],num)

if __name__ == "__main__":
    li = list(range(1,40,4))
    
    
    print(binary_search(li,23))


# def binary_search(alist, item):
#     if len(alist) == 0:
#         return False
#     else:
#         midpoint = len(alist)//2
#         if alist[midpoint] == item:
#           return True
#         else:
#           if item < alist[midpoint]:
#             return binary_search(alist[:midpoint],item)
#           else:
#             return binary_search(alist[midpoint+1:],item)

 

面试官:假如我找不到这个数,我需要返回这个数的所在区间,你怎么改:

答:再开两个变量,用以记录每次比较的 alist[mid],

def binary_search(alist,num,left=0,right=0):
    n = len(alist)

    if len(alist) == 0:
        return [left,right]
    mid = n // 2

    if alist[mid] == num:
        return True
    elif alist[mid] < num:
        left = alist[mid]
        return binary_search(alist[mid+1:],num,left,right)
    else:
        right = alist[mid]
        return binary_search(alist[0:mid],num,left,right)

还有一种就是让你返回和寻找的目标值接近的数,就比较一下左边界和由边界即可得到

上一篇:冒泡排序、选择排序、插入排序、快速排序、归并排序的思想与实现


下一篇:归并排序