二分查找

二分查找算法的条件是出现二段性。

二分查找的二段性（单调性）指的是：整个查找区间可以依据某个条件分成前后两段，其中一段全部满足某个性质 P，而另一段全部不满足 P，并且这两段之间有一个明确的分界点。

例 1：有序的（升序）整型数组 nums 和一个目标值 target，搜索 nums 中的 target，如果 target 存在返回下标，否则返回 -1

朴素的二分模板：

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

例 2：一个按照非递减顺序排列的整数数组 nums，找出第一个大于等于 target 的数字下标

C++提供了lower_bound库函数来解决对应问题

vector<int> nums = {1, 2, 66, 89, 100, 233};
cout << lower_bound(nums.begin(), nums.end(), 100) - nums.begin();  // 4
cout << lower_bound(nums.begin(), nums.end(), 500) - nums.begin();  // nums.size() = 6

思路 1：我们使用二分查找算法以及拓展(三种写法)：

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

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

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

查找条件通常可以归结为 >=(x)，所以有以下四种类型：

• >=(x)
• >(x) 转换 >=(x + 1)
• <(x) 转换 >=(x) - 1
• <=(x) 转换 >(x) - 1 转换 >=(x + 1) - 1

思路 2：查找左边界的二分和查找右边界二分模板：

// 查找左边界：
int search_left(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        int mid = (right - left) / 2 + left;
        if (condition)
            left = mid + 1;
        else
            right = mid;
    }
    return left;
}
// 查找右边界：
int search_right(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        int mid = (right - left + 1) / 2 + left;
        if (condition)
            left = mid;
        else
            right = mid - 1;
    }
    return left;
}

/**
问题1：查找左边界
1. 二段性：[< t][>= t]
- nums[mid] < t:left = mid + 1
- nums[mid] >= t:right = mid
2. 循环条件：
left == right就是答案，退出循环；right = mid，死循环
3. 中点计算：
个数为偶数，right = mid 死循环
--------------
问题1：查找右边界
1. 二段性：[<= t][> t]
- nums[mid] <= t:left = mid
- nums[mid] > t:right = mid - 1
2. 循环条件：
left == right就是答案，退出循环；left = mid，死循环
3. 中点计算：
个数为偶数，left = mid 死循环
*/

模板使用步骤：

1. 是否有二段性，能否使用二分算法
2. 进行区域划分，看求左边界还是右边界
3. 判断边界条件 condition 和指针移动，就题论题即可
4. 中点计算：出现了 -1 就 +1
5. 编写代码，返回值微调处理

上取整和下取整：

• ⌈ x / y ⌉ = (x - 1) / y + 1
• ⌊x / y ⌋ = x / y