制作企业网站的目的_省级精品课程网站_百度风云榜排行榜_关键词查找工具

二分查找

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;}
};

总结：

1. 能使用二分查找的前提是具有二段性，无论是否有序，重要的是有二段性
2. 判断循环的条件要注意，等于的时候也要进入循环，因为都是未知的，当left和right相等时，具体到一个数也要进循环判断
3. 在算mid时要防止溢出
4. 本题也是朴素二分查找的模板

while(left <= right) // 等于也要进入循环
{int mid = left + (right - left) / 2; // 防止溢出if(...) left = mid + 1;else if(...) right = mid - 1;else return ...;
}

5. …根据二段性来填写

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

class Solution 
{
public:vector<int> searchRange(vector<int>& nums, int target) {if(nums.size() == 0) return {-1, -1};int left = 0, right = nums.size() - 1;int begin = 0; // 用于记录左端点// 找左端点while(left < right){int mid = left + (right - left) / 2;if(nums[mid] < target) left = mid + 1;else right = mid;}if(nums[left] != target) return {-1, -1};else begin = left;// 找右端点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;}return {begin, right};}
};

总结：

1. 模板

// 找左端点
while(left < right)
{int mid = left + (right - left) / 2;if(...) left = mid + 1;else right = mid;
}// 找右端点
left = 0, right = nums.size() - 1; // 重置指针
while(left < right)
{int mid = left + (right - left + 1) / 2;if(...) left = mid;else right = mid - 1;
}

助记：下面-1，上面就加一，判断情况就题论题

2. 

x的平方数

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

总结：

1. 提前处理边界情况
2. 本题实际上是找左端点，所以想左端点重要，写出判断条件

搜索插入位置

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;}
};

总结：
本题实际是找左端点，需要注意的是要单独处理一下最后的特殊情况

山脉数组的峰顶索引

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;}
};

总结：

1. 数组具有二段性，想到二分查找
2. 直接用模板，下面减一上面加一

寻找峰值

class Solution 
{
public:int findPeakElement(vector<int>& nums) {int left = 0, right = nums.size() - 1;while(left < right){int mid = left + (right - left) / 2;if(nums[mid] > nums[mid + 1]) right = mid; //如果中间值大于下一个值，就去左边一段查找，体会二段性else left = mid + 1; // 否则去右边一段查找}return left;}
};

总结：
3. 上减下加，模板很固定，没有出现则不用加
4. 存在二段性就能用二分查找，不用管数组是否有序

寻找旋转排序数组的最小值

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

总结：
5. 本题主要是找见二段行，一定要画图，理解两段，找见参照点

点名

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;}return records[left] == left ? left + 1 : left; // 三目表达式的运用很方便}
};

总结：

1. 本题解法很多，如使用哈希表，遍历，位运算（异或），数组求和，二分法
2. 二分法关键是找二段性，本题的二段性在值和下标是否一一对应，注意要处理边界情况

---

完