二分查找算法
二分查找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 < target) left = mid + 1;
else if(nums > target) right = mid - 1;
else return mid;
}
return -1;
}
};
总结：
[*]能利用二分查找的前提是具有二段性，无论是否有序，紧张的是有二段性
[*]判定循环的条件要注意，即是的时候也要进入循环，因为都是未知的，当left和right相等时，具体到一个数也要进循环判定
[*]在算mid时要防止溢出
[*]本题也是朴素二分查找的模板
while(left <= right) // 等于也要进入循环
{
int mid = left + (right - left) / 2; // 防止溢出
if(...) left = mid + 1;
else if(...) right = mid - 1;
else return ...;
}
[*]…根据二段性来填写
在排序数组中查找元素的第一个和末了一个位置
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 < target) left = mid + 1;
else right = mid;
}
if(nums != 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 <= target) left = mid;
else right = mid - 1;
}
return {begin, right};
}
};
总结：
[*]模板
// 找左端点
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，上面就加一，判定环境就题论题
[*]https://i-blog.csdnimg.cn/direct/adeb62a4d9de46f9a72ce5591a6bfcd1.jpeg#pic_center
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;
}
};
总结：
[*]提前处理边界环境
[*]本题实际上是找左端点，所以想左端点紧张，写出判定条件
搜索插入位置
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 < target) left = mid + 1;
else right = mid;
}
if(nums < 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 > arr) left = mid;
else right = mid - 1;
}
return left;
}
};
总结：
[*]数组具有二段性，想到二分查找
[*]直接用模板，下面减一上面加一
探求峰值
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 > nums) 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 < nums) right = mid;
else left = mid + 1;
}
return nums;
}
};
总结：
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) left = mid + 1;
else right = mid;
}
return records == left ? left + 1 : left; // 三目表达式的运用很方便
}
};
总结：
[*]本题解法许多，如利用哈希表，遍历，位运算（异或），数组求和，二分法
[*]二分法关键是找二段性，本题的二段性在值和下标是否一一对应，注意要处理边界环境
完
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]