面试官:会二分查找吗?来,写一下
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)
还有一种就是让你返回和寻找的目标值接近的数,就比较一下左边界和由边界即可得到