算法修炼之路之二分查找
目录
一:三大二分介绍及模板
1.普通二分
这里通过一道题来引出普通二分及模板
画图分析:
具体代码:
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) right=mid-1;
else if(nums[mid]<target) left=mid+1;
else return mid;
}
return -1;
}普通二分模板
2.查找左右边界的二分及模板
通过题来引出
LeetCode_34 在排序数组中查找元素的第一个和最后一个位置
画图分析:
具体代码:
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) begin=left;//标记一下左端点
else return {-1,-1};
//查找右端点
left=0,right=nums.size()-1;
while(left<right)
{
int mid=left+(right-left+1)/2;
if(nums[mid]>target) right=mid-1;
else left=mid;
}
return {begin,left};
}左右边界的二分模板:
二:LeetCode OJ练习
1.第一题
画图分析:
具体代码:
int mySqrt(int x) {
//处理边界情况
if(x<1) return 0;
int left=1,right=x;//防止当x=INT_MAX时，right-0+1操作直接越界的
while(left<right)
{
long long mid=left+(right-left+1)/2;//防止越界
if(mid*mid>x) right=mid-1;
else left=mid;
}
return left;
}2.第二题
画图分析:
具体代码:
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;
}3.第三题
画图分析:
具体代码:
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;
}4.第四题
画图分析:
具体代码:
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;
}5.第五题
画图分析:
具体代码:
int findMin(vector<int>& nums) {
int left=0,right=nums.size()-1;
int t=nums[right];
while(left<right)
{
int mid=left+(right-left)/2;
if(nums[mid]>t) left=mid+1;
else right=mid;
}
return nums[left];
}6.第六题
画图分析:
具体代码：
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;
}原文地址：https://blog.csdn.net/Miwll/article/details/142721114
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！