由二分查找说起

二分查找一种时间复杂度为O(log n)的经典查找方法。大体步骤是先进行排序，然后定义两个指针：头指针和尾指针。每次比较头指针和尾指针对应区间内最中间的数值和查询数值的大小，即将搜查区间一分为二，然后这样排除一半的区间，从而提升查找效率。
python代码如下:

def bin_search(array,token):
    low = 0
    high=len(array)-1
    while low<=high:
        mid = (low+high)//2
        if array[mid]==token:
            return mid
        elif array[mid]<token:
            low = mid+1
        else: high = mid -1
    return -1

二分查找的算法本身非常简单，但是它的整体思路还是非常值得借鉴的，它的双指针结构和分治思路在很多题目中经常被应用到，尤其是追求更好的时间复杂度的算法。

应用一 求一个递增数组中某个数值的数目。

比如1，1，2，4，4，4，5 这样的一列数组，4出现的个数。
这个问题传统的思路是从左到右依次依次线性查找，这样时间复杂度为o(n)。使用上面的二分查找的思路，可以分为两步分，首先找到检索值第一次出现的下标a，然后找到检索值最后依次出现的下标b，b-a+1就是所求的结果。这种思路用到了两次二分查找，不同是在array[mid]== token时并不是直接返回，而是存储到result变量中，同时分别改变low(low=mid+1)和high(high=low-1)的值(对应求最左和最右两种情况)，继续loop，直到最终不满足low<=high而跳出循环，最终的result即为我们需要的最左(或者最右元素的index)

应用二 求循环数组的循环次数。

例如[3,4,5,1,2]可以看做[1,2,3,4,5]向右循环移动3次的结果，这个问题是根据循环后的结果求解循环次数。该问题可以转换为查找循环数组的最小值对应的index，正好是循环移位的次数。
解决思路同样是二分查找，只不过循环体中不仅仅根据mid进行判断，同时增加了两个值 pre 和next ，分别对应mid前一位和后一位的坐标。
代码如下：

def cal_times(a):
    length = len(a)
    low = 0
    high = length - 1
    while low<=high:
        mid = low+(high-low)//2
        if a[low]<=a[high]:
            return low
        prev = (mid-1+length)%length
        next = (mid+1)%length
        if a[mid]<a[prev] and a[mid]<a[next]:
            return mid
        elif a[mid]<a[low]:
            high = mid -1
        else:
            low = mid +1

是不是看起来非常清爽呢？

说一点点题外话和人生感悟，二分查找的思路也可以应用在我们生活中。当我们找不到通往人生目标的道路时，可以借鉴二分查找，把所有人生可能尝试的方向分成两大类，一类是和目标无关的领域，一类是可能相关的领域，无关的累赘的部分大胆的舍弃，然后在剩下的部分中继续探索，直到快速找到我们的通往目标的道路，这样比我们一个个都尝试一遍效率高很多。简而言之就是有不为才能有所为。人生在世，适当的做一些减法，抛弃一些身外之物，这样可以走的更快。

PS:感谢我的sweet heart 😘给我重新开启简书之旅的契机，你的陪伴是我坚持的动力。从今日开始，每天都写点东西，希望各位看客多多支持~😁