1.二分查找
思路：
朴素二分模版
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while(l <= r)
{
int mid = (l + r) / 2;
if(nums[mid] < target) l = mid + 1;
else if(nums[mid] > target) r = mid - 1;
else return mid;
}
return -1;
}
};2.在排序数组中查找元素的第一个和最后一个位置
思路：
二分左端点和二分右端点模版题
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
// 处理边界情况
if(nums.size() == 0) return {-1, -1};
// 记录开始位置
int begin = 0;
// 二分左端点
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 {-1, -1};
else
begin = left;
// 更新right位置
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, left};
}
};3.搜索插入位置
思路：
根据插入位置来分析出一个二分性
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;
else return left;
}
};4.x的平方根
思路：
记得处理边界情况
class Solution {
public:
int mySqrt(int x) {
//处理边界情况
if(x < 1) return 0;
int left = 1, 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.山顶数组的封顶索引
思路：
切记首位置和最后一个位置无需二分
二分查找并不需要完全按照有序的性质来确定是否使用，
我们只需要找出一个二分性就可使用二分查找算法。
class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr) {
int left = 1, right = arr.size() - 2;
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.寻找峰值
思路：
二分右端点
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]) left = mid + 1;
else right = mid;
}
return left;
}
};7.寻找旋转数组中的最小值
思路：
旋转数组，可以画个图
以一个参照点来找出二分性
以最右边端点为参照最合适，无需考虑边界问题
当选择左边端点时需要考虑当一个旋转 数组刚好就是原数组时，需要特别处理！
class Solution {
public:
int findMin(vector<int>& nums) {
int x = nums[nums.size() - 1];
int left = 0, right = nums.size() - 1;
while(left < right)
{
int mid = left + (right - left) / 2;
if(nums[mid] > x) left = mid + 1;
else right = mid;
}
return nums[left];
}
};8.点名
思路：
这个题解法有很多种！
1.暴力查找
2. 哈希表
3.位运算
4.二分查找
class Solution {
public:
int takeAttendance(vector<int>& r) {
int left = 0, right = r.size() - 1;
while(left < right)
{
int mid = left + (right - left) / 2;
if(r[mid] == mid) left = mid + 1;
else right = mid;
}
//处理细节问题
if(r[left] == left) return left + 1;
else return left;
}
};
