代码随想录：704. 二分查找
题目链接：704. 二分查找
题目描述
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果 target 存在返回下标，否则返回 -1。
你必须编写一个具有 O(log n) 时间复杂度的算法。
示例 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
提示：
你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。
点击查看代码
//左闭右闭
class Solution {
public:int search(vector<int>& nums, int target) {int left = 0;int right = nums.size() - 1;while(left <= right){int middle = (left + right) / 2;if(target == nums[middle]) return middle;else if(target > nums[middle]) left = middle + 1;else right = middle - 1;}return -1;}
};//左闭右开
class Solution {
public:int search(vector<int>& nums, int target) {int left = 0;int right = nums.size();while(left < right){int middle = (left + right) / 2;if(target == nums[middle]) return middle;else if(target > nums[middle]) left = middle + 1;else right = middle;}return -1;}
};
小结
二分查找
将一个已排序，无重复的数组，通过 left 和 right，缩小目标值区间范围
将 target 与 nums[middle] 比较，确定目标值，更新左右边界
注意点
关于循环终止条件
whiile() 中是 left<=right 还是 left<right
将nums[middle] 与 target 比较，然后重新确定边界。在不断更新循环条件，而循环条件应当是不变的，所以应与第一次循环边界能否取到一致。第一次循环时左右边界又与初始化有关，由于left是一直可以取到，所以只要看right取值。若right取值为nums.size()-1说明右边界可以取，接下来循环时也要取到right。若right取值为nums.size(),取不到右边界，那么循环时也不能取到right。
关于 right 的更新是否包含middle
right = middle - 1 还是 right = middle
right的更新就与循环条件有关。若循环条件中right可以取到，则right更新时应取middle-1。若循环条件中right取不到，则right更新时应取middle，这样在下一次循环中，right边界不会取到，可以取到实际可能为目标值的right－1
实际上还是与right的初始化有关，right的初始化决定了右边界是否可以取到