合并两个有序序列

写出二分查找算法

已知函数原型：

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

要求补全上述代码

注意事项：

1. (left+right) //2 ，更好写法：left + (right-left)//2
2. 迭代中，一定注意while判断中等号问题
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: # 严格大于
            right = mid - 1 
        else: # 此处严格小于
            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: # 严格小于
        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)  
  

更多演示动画

能找到关键码：

不能找到关键码：

    

合并两个有序数组 left 和 right：

def merge(left,right):
  #补全代码
  #
  return temp 

思路可参考示意图：