Day 19：合并两个有序数组

Day 19 合并两个有序序列

Day 18 作业总结

写出二分查找算法

已知函数原型：

代码语言：javascript复制

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

要求补全上述代码

注意事项：

1. (left right) //2 ，更好写法：left (right-left)//2
2. 迭代中，一定注意while判断中等号问题
3. 二分查找的代码还是很容易写出bug

迭代二分查找

代码参考星友 Leven：

代码语言：javascript复制

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)

递归二分查找

代码语言：javascript复制

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)

更多演示动画

能找到关键码：

不能找到关键码：

Day 19 作业题

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

代码语言：javascript复制

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

思路可参考示意图：

bug 递归 动画 原型

0 人点赞