最近2018中文字幕在日韩欧美国产成人片_国产日韩精品一区二区在线_在线观看成年美女黄网色视频_国产精品一区三区五区_国产精彩刺激乱对白_看黄色黄大色黄片免费_人人超碰自拍cao_国产高清av在线_亚洲精品电影av_日韩美女尤物视频网站

合并兩個(gè)有序序列

寫出二分查找算法

已知函數(shù)原型：

def binary_search(arr,left,right,hkey):
    pass 

要求補(bǔ)全上述代碼

注意事項(xiàng)：

1. (left+right) //2 ，更好寫法：left + (right-left)//2
2. 迭代中，一定注意while判斷中等號(hào)問題
3. 二分查找的代碼還是很容易寫出bug

迭代二分查找

代碼參考星友 Leven：

def binary_search(arr,left,right,hkey):
    while left <= right:
        mid = left + (right-left) // 2
  
        if arr[mid] == hkey:
            return mid
        elif arr[mid] > hkey: # 嚴(yán)格大于
            right = mid - 1 
        else: # 此處嚴(yán)格小于
            left = mid + 1  
            
    return -1 # 表示找不到
if __name__ == "__main__":
    sorted_list = [1,2,3,4,5,6,7,8]
    result = binary_search(sorted_list,0,7,4)
    print(result)  

遞歸二分查找

def binary_search(arr,left,right,hkey):
    if len(arr) == 0:
        return -1
  
    if left > right:
        return -1
  
    mid = left + (right-left) // 2
 
    if arr[mid] == hkey:
        return mid
    elif arr[mid] < hkey: # 嚴(yán)格小于
        return binary_search(arr,mid+1,right,hkey) # 折半
    else:
        return binary_search(arr,left,mid-1,hkey)

if __name__ == "__main__":
    sorted_list = [1,2,3,4,5,6,7,8]
    result = binary_search(sorted_list,0,7,4)
    print(result)  
  

更多演示動(dòng)畫

能找到關(guān)鍵碼：

不能找到關(guān)鍵碼：

    

合并兩個(gè)有序數(shù)組 left 和 right：

def merge(left,right):
  #補(bǔ)全代碼
  #
  return temp 

思路可參考示意圖：