理论篇-不容易写对的二分查找

前面我们介绍了那么多的排序算法，那对数据排序有什么用呢？这篇文章介绍一个专门针对有序序列的效率极高的查找算法: 二分查找。

核心思想: 首先，找到中间元素，将整个序列分为三部分: 小于等于中间元素的子序列+中间元素+大于等于中间元素的子序列。如果中间元素不是要查找的元素，则根据查找元素与中间元素的关系来决定是在哪个子序列中查找。直到找到或子序列不能分为止。

int
binary_search(int *a, int start, int end, int x) {
    int mid;
    
    while (start <= end) {
        mid = (start+end)/2;
        if (a[mid] == x) return mid;
        if (a[mid] > x) end = mid - 1;
        if (a[mid] < x) start = mid + 1;
    }
    
    return -1;
}

备注: 循环截止的条件必须是小于等于，假设数组只有一个元素，此时必须进入循环，判断该元素是不是要查找的值。