Day 18：二分查找算法

Day 17 作业题总结

写出几种常见复杂度对应的算法，星友们给出的答案都很准确，在这里参考星友聂磊的答案：

时间复杂度：

常见操作：哈希查找，数组取值，常数加减乘除

: 二分查找

计算数组中所有元素和，最大，最小

：归并排序，堆排序，希尔排序，快速排序

：冒泡，选择排序

：三元方程暴力求解

：求解所有子集

：全排列问题。比如：给定字母串，每个字母必须使用，且一次组合中只能使用一次，求所有组合方式；另外还要经典的旅行商 TSP 问题

下面这幅图太直观了：

其中，复杂度为： ， 是难解的问题， , 都是可以接受的解， , 的解是梦寐以求的。

Day 18 ：二分查找

二分查找算法，binary search algorithm，也称「折半搜索算法」、「对数搜索算法」

它的使用前提：是一种在「有序数组」中查找某一特定元素的搜索算法。

请补全下面二分查找算法：

# 返回hkey在数组中的索引位置
def binary_search(arr, left, right, hkey):
    """
    arr：有序数组
    left：查找区间左侧
    right：查找区间右侧
    hkey：带查找的关键码
    备注：left, right 都包括在内，找不到返回 -1
  
    """
    #
    #
    #