【刷题】-- 基础 -- 二分查找

精于结构、敏于心智、熟于代码

        方式：对于会的代码：学会以最快的速度构建，并以最快的速度书写；对于不会的代码：学会（以最短的路径下）看懂别人的代码。学会使用参考文档、熟悉每一个容器。

刷题位置：「算法」 - 学习计划 - 力扣（LeetCode）全球极客挚爱的技术成长平台

---

对于二分查找问题的基础解决思路：（特点：遍历都可以进行解决 －> 问题：时间复杂度相较于过大）

1. 查找的过程，本质就是排除的过程。（一次排除一批）
2. 抓紧题目所给的关键特点。（排列方式，查询特点）
3. 以while循环查找 －> 找到了 / 确定查找范围的边界。（循环结束的条件）

704. 二分查找

        给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9输出: 4
解释: 9 出现在nums中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2输出: -1
解释: 2 不存在 nums 中因此返回 -1

针对于本题：

关键点：我们需要在一个升序的数组中找到一个值是否存在。

核心：

1. 可以通过左小右大进行，中间位置的log2的缩小范围。
2. left的范围跟新为 mid + 1，right的范围跟新为 mid + 1。
3. 整个范围找完即 left > right 此时无该值。

特殊点：

1. 只有一个值的时候 / right 更新 (mid - 1) == left，恰好值是left位置，对left同理 -> while循环增加一个left = right是至关重要的。
2. 防止数组大小为空（此题说了size >= 1，此处就没事）。
3. 最好别写为mid = (right + left) / 2，因为有 (right + left) 会导致数据过大。 

class Solution {
public:int search(vector<int>& nums, int target) {// 保证比较的位置是有效数据段中的中间位置int left = 0, right = nums.size() - 1;int mid = right / 2;//if(nums.empty())//    return -1;// 左的下标大于右，即有效数据段比完了：left < right// 防止出现只有一个数据、如right = mid + 1 == left -> nums[left] == target的时候。while(left <= right){// 移动左右下标到有效区域if(nums[mid] < target)left = mid + 1;else if(nums[mid] > target)right = mid - 1;elsereturn mid;mid = left + (right - left) / 2;}return -1;}
};

复杂度分析

• 时间复杂度：O(log⁡n)，其中 n 是数组的长度。

• 空间复杂度：O(1)。

类似题

374.猜数字大小

猜数字游戏的规则如下：

每轮游戏，我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）：

-1：我选出的数字比你猜的数字小 pick < num。
1：我选出的数字比你猜的数字大 pick > num。

0：我选出的数字和你猜的数字一样。恭喜！你猜对了！pick == num。

返回我选出的数字。

​​​​​​

/** * Forward declaration of guess API.* @param  num   your guess* @return 	     -1 if num is higher than the picked number*			      1 if num is lower than the picked number*               otherwise return 0* int guess(int num);*/class Solution {
public:int guessNumber(int n) {int left = 1, right = n;int mid = left + (right - left) / 2;while(left <= right){if(guess(mid) == 0)return mid;else if(guess(mid) == 1)left = mid + 1;elseright = mid - 1;mid = left + (right - left) / 2;}return -1;}
};

278.第一个错误的版本

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);class Solution {
public:int firstBadVersion(int n) {uint64_t left = 1, right = n;uint64_t mid = (right + left) / 2;while(left <= right){if(!isBadVersion(mid) && !isBadVersion(mid + 1)){left = mid + 1;else if(isBadVersion(mid) && isBadVersion(mid - 1))right = mid - 1;elseif(isBadVersion(mid))return mid;elsereturn mid + 1;mid = left + (right - left) / 2;}return -1;}
};

按照常见二分查找的书写，上面的题肯定是可以对的，但是有点过于的臃肿，效率是够的，但是对于程序员是不友好的，所以我们可以进行优化一下。

特殊点：

此处由于我们需要第一个 bool isBadVersion(version) 为对的， 所以对与right我们可以right = mid，因为我们无法确定它是不是第一个，所以我们不能排除掉它。对于left的 bool isBadVersion(version) 为错，不需要，即：left = mid + 1。

一个right = mid，另一个left = mid + 1，则left == right时就找到了。

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);class Solution {
public:int firstBadVersion(int n) {int left = 1, right = n;while(left < right){int mid = left + (right - left) / 2;if(isBadVersion(mid))right = mid;elseleft = mid + 1;}// 此时left == rightreturn left;}
};

针对上述的类似写法我们还可以解决一个题。

35.搜索插入的位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

class Solution {
public:int searchInsert(vector<int>& nums, int target) {int left = 0, right = nums.size();while(left < right){int mid = left + (right - left) / 2;if(target < nums[mid])right = mid;elseleft = mid + 1;}// left == rightif(left && nums[left - 1] == target)return left - 1;return left;}
};