博客主页: 酷酷学!!!
感谢您的关注~

---

正文开始

1. 朴素版: 二分查找

题目思路: 仅需根据题意, 找出二段性, 正确更新下标位置即可.

class Solution {
public:int search(vector<int>& nums, int target) {int left = 0, 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;}
};

---

2. 查找排序数组元素第一个和最后一个位置

算法原理:

那么本道题朴素的二分查找就不适用了, 我们需要根据二段行将数组进行划分, 得到下图结论.

这里的注意事项细节处理, 循环条件以及我们的求中点操作, 那么为什么这种算法就是对呢?

下面我们可以通过三种情况来细分, 如果有结果则相遇位置就是结果, 如果全大于t, 则会一直right向左移动最后相遇位置结束, 退出循环, 全小于t, 则left会一直向右移动, 最后退出循环, 那么为什么求左端点第二种求中点操作死循环呢?

int mid = left + (right - left + 1)/2, 对于这种写法, 假设剩下最后两个元素, 这两区别无非就是一个拿到前一个元素, 一个拿到后一个元素, 如果我们要求左端点拿到后面的元素, 如果muns[mid] < target. left会变成mid+1, 出循环, 如果nums[mid] <= target,则right会一直等于mid的位置, 陷入死循环.

故, 求右端点类似

总结一下: 如何让二分从恶心变成easy~

编写代码:

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {if(nums.empty()) return {-1,-1};//处理为空的情况int left = 0 ,right = nums.size() - 1;int begin = 0, end = 0;while(left < right){int mid = left + (right - left)/2;if(nums[mid] < target)left = mid + 1;else right = mid;}begin = left;if(nums[left] != target) return {-1,-1}; //处理未找到的情况right = nums.size() -1;while(left < right){int mid = left + (right - left + 1)/2;if(nums[mid] <= target)left = mid;else right = mid - 1;}end = left;return {begin,end};}
};

---

3. 搜索插入位置

算法思路:

根据题目我们很容易发现二段性, 需要待插入的位置就为左端点, 注意, 如果所有数据都小于target则相遇位置为最后一个位置, 待插入位置为相遇位置的下一个位置.

编写代码:

class Solution {
public:int searchInsert(vector<int>& nums, int target) {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[left] < target) return left + 1;return left;}
};

---

4. x的平方根

算法思路:

我们根据题意不难找出二段性, 要查找的位置为右端点, 列出判断语句即可.

编写代码:

class Solution {
public:int mySqrt(int x) {long long left = 0, right = x;while(left < right){long long mid = left + (right - left + 1) / 2; if(mid * mid <= x)left = mid;else right = mid - 1;}return left;}
};

---

5. 山脉数组的峰顶索引

算法思路:

根据二段性, 分出左右数组, 注意如果判断语句中有-1, 则计算mid有+1.

编写代码:

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

---

6. 寻找旋转数组中的最小值

算法思路:

以最后一个数为基准值进行比较, 即可将数组划分成两部分, 这里不可以以nums[0]进行划分, 因为当数组有序时, 相遇位置会在最后一个位置导致结果错误, 需要特殊处理.

编写代码:

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

---

以nums[0]为基准值划分

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

---

7. 点名

算法思路:

本道题解法多种, 但是二分查找时间复杂度最低, 根据题目不难发现根据下标即可划分出数组, 但是注意判断, 当数组有序时, 缺失位置为最后一个位置的下一个位置, 这里指针相遇的位置需要最后+1.

编写代码:

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

---

完, 感谢点赞收藏!!!