二分查找总结

二分查找是一个非常基础的算法，但是每次写边界总要想一下，特别是用二分查找来寻找上下界的时候。

查找一个元素是否存在

代码：

int binarySearch(const vector<int> &arr, int x) {
    int left = 0, right = arr.size() - 1;
    int index = -1;
  	// 注意循环结束条件
    while (left <= right) {
        int mid = (right - left) / 2 + left;
        if (arr[mid] == x) {
            index = mid;
            break;
        } else if (arr[mid] < x) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return index;
}

这里的边界是left<=right，因为在循环体中left和right都会在mid的基础上加1或减1，所以left最终会大于right。

考虑left = 4, right = 5，计算后mid = 4。如果右边界要改变，right = mid - 1 = 3 < left跳出循环，如果要改变左边界left = mid + 1 = 5 = right，下一次必定可以打破条件跳出。

查找上下界

二分查找也可以用来查找相同元素的上下界。没总结之前觉得边界条件好复杂，总结之后其实很简单。

寻找上界代码：

int binarySearchUpbound(const vector<int> &arr, int x) {
    // 注意right初始
    int left = 0, right = arr.size();
    // 注意循环终止条件
    while (left + 1 < right) {
        int mid = (right - left) / 2 + left;
        // important
        if (arr[mid] <= x) {
            left = mid;
        }
        else {
            right = mid;
        }
    }
    if (arr[left] == x) return left;
    else return -1;
}

因为循环体中，right和left都不会在mid的基础上做改变，如果left + 1 = right，采用left <= right的这种方式作为循环结束条件就会死循环。

在寻找上界的时候，希望left最终存的是上界的下标，这个时候需要把等于号放在左边界上。

寻找下界代码：

int binarySearchLowbound(const vector<int> &arr, int x) {
    // 注意left初始
    int left = -1, right = arr.size() - 1;
    // 注意循环终止条件
    while (left + 1 < right) {
        int mid = (right - left) / 2 + left;
        // important
        if (arr[mid] >= x) {
            right = mid;
        }
        else {
            left = mid;
        }
    }
    if (arr[right] == x) return right;
    return -1;
}

与寻找上界不同，寻找下界的时候希望right最终保存下界下标，这个时候需要把等号放在右边界上。

另外：注意到，寻找上下边界的时候left和right初值设置是不一样的。寻找上边界初始right = n，指向数组末尾后面一个元素，寻找下边界时初始left = -1。这是为了防止整个数组都是一样的值，如果数组值都一样，那寻找上边界时right的就是上边界，left可能永远到不了上边界。寻找下边界时也会出现同样的情况。