注意计算mid时的整形溢出
边界值判断
数组必须时有序的
时间复杂度O(logn)
二分方式：二分下标，二分答案

1. 基本二分查找

局限性：无法查找target的左右侧边界

int binarySearch(vector<int>& nums, int target)
{
    int left = 0;
    int right = nums.size() - 1;
    while (left <= right) {
        int mid = (right - left) / 2 + 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;
}

2. 寻找左侧边界

// 寻找数组中最左边的目标[1, 2, 2, 2, 3]中index = 1的2
// [left, right]写法
int binarySearch(vector<int>& nums, int target)
{
    int left = 0;
    int right = nums.size() - 1;
    while (left <= right) {
        int mid = (right - left) / 2 + left;
        if (nums[mid] == target) {
            right = mid - 1; // 收缩右侧边界
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        }
    }
    // 左侧边界的概念：nums小于target的个数有left个
    // left 可能是0，代表比target小的有0个
    // left 也可能是nums.size(),代表都比target小
    if (left >= nums.size() || nums[left] != target) {
        return -1;
    }
    return left;
}

3. 寻找右侧边界

// 寻找数组中最右边的目标[1, 2, 2, 2, 3]中index = 3的2
// [left, right]写法
int binarySearch(vector<int>& nums, int target)
{
    int left = 0;
    int right = nums.size() - 1;
    while (left <= right) {
        int mid = (right - left) / 2 + left;
        if (nums[mid] == target) {
            left = mid + 1; // 收缩左侧边界
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        }
    }
    // 右侧边界的概念：nums小于等于target的个数有right个
    // right 可能是nums.size() - 1，代表比target大的有0个
    // right 也可能是-1,代表都比target大
    if (right < 0 || nums[right] != target) {
        return -1;
    }
    return right;
}

4. 二分查找函数

#include <algorithm>
vector<int> a = {1, 3, 3, 5, 7};
vector<int>::iterator it = lower_bound(a.begin(), a.end(), 3); // index = 1, 查找有序区间a[i] >= k的最小指针
vector<int>::iterator it = upper_bound(a.begin(), a.end(), 3); // index = 3, 查找有序区间a[i] > k的最小指针
bool ret = binary_search(a.begin(), a.end(), 3); // ret = true, 查找有序区间是否存在val。
// 注意查找区间：左闭右开，有序。适用于set\map\vector
// 函数lower_bound()在first和last中的前闭后开区间进行二分查找，返回大于或等于val的第一个元素位置。如果所有元素都小于val，则返回last的位置，且last的位置是越界的！
// 要计算下标pos，需要减去a.begin()，pos的可能值是[0, a.size()], 注意a.size()是越界的、代表所有值都比val小
int pos = lower_bound(a.begin(), a.end(), 3) - a.begin(); 
int b[5] = {1, 3, 3, 5, 7};
int pos = lower_bound(b, b + 5, 3) - a;
// 计算长度为n的有序数组a中k的个数，可以为0
int num = upper_bound(a.begin(), a.end(), 3) - lower_bound(a.begin(), a.end(), 3);
// 将有序数组a中k所对应位置的元素改为k;
*lower_bound(a.begin(), a.end(), k) = k;
// 查找第一个最大值/最小值的地址，有相同大小的元素，找第一个
vector<int>::iterator it = max_element(a.begin(), a.end());
vector<int>::iterator it = min_element(a.begin(), a.end());
// 查找第一个最大值/最小值的下标
int pos = max_element(a.begin(), a.end()) - a.begin();
int pos = min_element(a.begin(), a.end()) - a.begin();
// 查找第一个最大值/最小值
int maxNum = *max_element(a.begin(), a.end());
int minNum = *min_element(a.begin(), a.end());

// 编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
// 每行中的整数从左到右按升序排列。
// 每行的第一个整数大于前一行的最后一个整数。
class Solution {
public:
    // 将二维数组转化为一维数组的方式
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        int n = matrix[0].size();
        int left = 0;
        int right = m * n - 1;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            if (matrix[mid / n][mid % n] == target) {
                return true;
            } else if (matrix[mid / n][mid % n] < target) {
                left = mid + 1;
            } else if (matrix[mid / n][mid % n] > target) {
                right = mid - 1;
            }
        }
        return false;
    }
};