相信我们都在编程过程中遇见查找问题，而查找的方式有许多种，我们最常见的、也是使用次数最多的便是二分查找了，原理简单且不容易超时。
二分查找的思想很容易理解，但大多数人都是通过记模板来使用，这篇博客将二分法做一个大概的总结，以供记忆和复习。

一、分享小故事

这里引用了CSDN中Charon_cc的一个很生动形象的例子：

有一天小明到图书馆借了 N 本书，出图书馆的时候，警报响了，于是保安把小明拦下，要检查一下哪本书没有登记出借。小明正准备把每一本书在报警器下过一下，以找出引发警报的书，但是保安露出不屑的眼神：你连二分查找都不会吗？于是保安把书分成两堆，让第一堆过一下报警器，报警器响；于是再把这堆书分成两堆…… 最终，检测了 logN 次之后，保安成功的找到了那本引起警报的书，露出了得意和嘲讽的笑容。于是小明背着剩下的书走了。 从此，图书馆丢了 N - 1 本书。

多读两遍我们就会发现二分查找法的前提：

二、二分查找的前提

  • 查找的目标只能有一个
  • 查找的范围内元素是有序的（排序在C++里可以直接使用sort，而在C里可以使用冒泡排序等方法）

为什么是这样的一个前提呢？我们首先应该知道二分查找的原理：

三、二分查找的原理

在一个已经从小到大排好的数组里，先把目标与数组中间值比较
* 若目标>中间值，则接着找后半部分，前半部分舍弃。
* 若目标<中间值，则接着找前半部分，后半部分舍弃。

那有初学的朋友会问了：数组元素数是偶数的话怎么取中间值？

其实不必纠结这个问题，因为每次都丢掉数组的一半的话，这个问题是一定会出现的。

虽说叫二分查找，但并不是说我们必须严格的取一半，只是取一半时舍弃掉的不合要求的元素最多，比较节约时间而已。
而由于我们使用int类型，每次取的就是最中间两个数中靠左的那个，这样一来无非是在搜索的范围里多加一个数而已，只要我们继续进行二分查找并找好边界值，就永远不会有元素被落下。

四、二分查找的使用

这里只写我最常用的一种方式：[left,right]式
使用int函数进行运算：

int binarysearch(int arr[],int size,int target)
{
    //size 可使用int size=sizeof(arr)/sizeof(arr[0])计算

    int l=0,r=size-1;   //l=left,r=right,m=middle
    while(l<=r){
        int m=l+(r-l)/2;    //防止直接相加导致溢出
        if(arr[m]>target){
            r=m-1;
        }
        else if(arr[m]<target){
            l=m+1;
        }
        else
            return m;
    }
    return -1;
}

五、二分查找的性能

  • 时间复杂度：O(1)~O(log2n)
  • 空间复杂度：O(1)~O(log2n)