几个模板

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

基础框架

int binarySearch(vector<int> nums, int target) {
    int left = 0, right = ...;
    while(...) {
        int mid = ((right - left) >> 1) + left;
        if (nums[mid] == target) {
            ...
        } else if (nums[mid] < target) {
            left = ...
        } else if (nums[mid] > target) {
            right = ...
        }
    }
    return ...;
}

二分查找大概有三种模板，它们的区别在于框架中 ... 位置的不同。

模板1

此模板是基础模板，即查找一个数，若能找到则返回下标；若找不到，则返回 -1。

int binarySearch(vector<int> nums, int target) {
    int left = 0;
    int right = nums.size() - 1; // 注意
    while(left <= right) {
        int mid = ((right - left) >> 1) + left;
        if(nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1; // 注意
        } else if (nums[mid] > target) {
            right = mid - 1; // 注意
        }
    }
    return -1;
}

左右边界

本模板的右边界为 int right = nums.size() - 1 ，搜索区间为 [left,right]；
还有一种的右边界为 int right = nums.size() ，搜索区间为 [left,right)；

循环条件

本模板的搜索区间为 [left,right]，对应循环条件是 left <= right ，原因如下：
left <= right 的终止条件是 left == right + 1 ，此时搜索区间为 [right + 1, right] ，显然此时终止循环是正确的。
若改为 left < right ，则终止条件是 left == right ，此时搜索区间为 [right, right] ，会漏掉 right 这种情况。

边界值的修改

注意到 left = mid + 1 和 right = mid - 1 ，为什么不是 left = mid 和 right = mid 呢？
我们对边界值进行修改的时候，mid 肯定不是我们要找的数，因此我们的搜索区间变成了 [left,mid) 和 (mid,right] 即[left,mid - 1] 和 [mid + 1,right] 。

适用范围

查找某个值出现的位置。

模板2

int binarySearch(vector<int> nums, int target) {
    int left = 0;
    int right = nums.size(); // 注意
    while(left < right) {
        int mid = ((right - left) >> 1) + left;
        if(nums[mid] == target) {
            right = mid; // 注意
        } else if (nums[mid] < target) {
            left = mid + 1; // 注意
        } else if (nums[mid] > target) {
            right = mid; // 注意
        }
    }
    return left;
}

适用范围

有序数组查找插入位置，或者是左边界。如 [1,2,2,2,3] target = 2 ，会返回 1 。

原理

当 nums[mid] == target 时不直接返回，而是 right = mid ，即缩小上界在 [left, mid) 中继续搜索，搜索区间不断逼近左边界，最终达到左边界。

返回值

返回 left 与返回 right 一样，因为循环终止的条件为 left == right 。
如果想让未找到时返回 -1 ，则可以将最后的 return left; 改为：

if (left == nums.size()) return -1;
return nums[left] == target ? left : -1;

模板3

int binarySearch(vector<int> nums, int target) {
    int left = 0;
    int right = nums.size(); // 注意
    while(left < right) {
        int mid = ((right - left) >> 1) + left;
        if(nums[mid] == target) {
            left = mid + 1; // 注意
        } else if (nums[mid] < target) {
            left = mid + 1; // 注意
        } else if (nums[mid] > target) {
            right = mid; // 注意
        }
    }
    return left - 1;
}

适用范围

查找右侧边界。或者是 nums 中 小于等于 target 的第一个数（无论是否能找到）。

原理

与模板2同理。

返回值

left - 1 ，因为 left = mid + 1 所以要减一。
如果想让未找到时返回 -1 ，则可以将最后的 return left - 1; 改为：

if (left == 0) return -1;
return nums[left - 1] == target ? (left - 1) : -1;