704.二分查找

704. 二分查找 - 力扣（LeetCode）

题目解析：

这道题其实用暴力其实很简单，挨个对比就完事了~

但我们可以利用其升序的特性对其进行优化：

随机选择一个数（5），发现比目标值（9）小那么这就意味着红线所画的部分全部都不用考虑了，5前面只会是比它还小的数，而利用该特性我们排除一个数的时候可以顺带排除另外一匹数。

算法解析：

我们设置一个变量mid，尽量让它指向中间部分。然后我们再根据题意把数组划分为两个区间，一个为符合区间，另一个为不符合区间。二分的本质就是不断舍弃不符合区间，然后在符合区间内进行再次划分为2区间，直到找到目标数为止。

代码：

class Solution {
public:int search(vector<int>& nums, int target) {int left = 0;int right = nums.size() - 1;//循环持续到双指针指向同一个数为止while (left <= right){//避免溢出的另一种取中写法int mid = left + (right - left) / 2;if (nums[mid] < target){left = mid + 1;}else if (nums[mid] > target){right = mid - 1;}else{return mid;}}return -1;}
};

 

34. 在排序数组中查找元素的第一个和最后一个位置

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

题目解析：

本题会发现无法像上一题那样用二分查找，因为该题是要返回重复数字的起始与终点位置，所以我们尝试把这个过程给拆分开来，先求左区间端点，再求右区间端点。

算法解析：

既然是找左端点，那肯定得保证从左边开始的数是能够划分在一起的。所以我们规定两个区间，一个区间内都是小于t的数，另一个区间都是大于等于t的数。

• 当我们所挑选的mid落入小于t的区间时，由于是没有结果的区间，只要让left跳出该区间即可。
• 当我们所挑选的mid落入大于等于t的区间时，由于是有结果的区间，right只需要跟紧mid即可。

循环细节处理：

当mid落入条件2时，left与right会是同一指向。但这个题无法在相等时候立刻返回结果，因为要返回两个范围。所以如果left与right相等那就会重新进入循环一直达成条件2，造成死循环。

所以真正的循环条件应该是：left<right

中点细节处理：

如果mid为第二种取法，那么当mid落入条件2时，right会留在原地并且循环仍会继续，就这样一直落入条件2，造成死循环。

所以正确的中点取法应该为：mid = left+(right-left)/2

当我们要求右端点时，那就得保证到右边截止都有一段连续的数。

• 当mid落入小于等于t的区间内时，由于是有结果的区间，left跟紧mid即可。
• 当mid落入大于t的区间内时，由于是没有结果的区间，right跳出区间即可。

中点细节处理：

当中点取法选择第一种时，会让mid落入条件2，left留在原地。这样会一直进入循环使得mid一直处于条件2中，造成死循环。

 所以正确的中点取法应该为：mid = left+(right-left+1)/2

代码：

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {vector<int> ret;//特殊情况判断if (nums.size() == 0){return { -1,-1 };}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;}}if (nums[right] != target){return { -1,-1 };}//加入起始点else {ret.push_back(right);}//范围重置left = 0;right = nums.size() - 1;//求右区端点while (left < right){//注意中点取法int mid = left + (right - left + 1) / 2;if (nums[mid] <= target){left = mid;}else {right = mid - 1;}}//加入结尾点ret.push_back(left);return ret;}
};