被代码按在地上敲

被代码按在地上敲

【LeetCode刷题】专题三:二分查找模板-LMLPHP

专题三:二分查找模板:

根据题干分析,根据二分性,划分区间,得出二分最重要的几个要点:
  1. 判断条件:while(......)left<=right 还是left<right。这是第一个容易死循环的点。
  1. 求中点的方式:mid = left + (right-left)/2 还是 mid = left + (right-left+1)/2这个点很关键。如果和下面mid的迭代不相符,这便是第二个死循环的点。
  1. left和right的迭代:是left = mid还是left = mid+1、是right = mid还是right = mid -1这都是需要清除的问题。

1. 朴素二分模板:

while (left <= right)
{
	int mid = left + (right - left) / 2;
	if (......)
		right = mid - 1;
	else if (......)
		left = mid + 1;
	else
		return mid;
}

2. 区间左值模板:

特点: 左值:左动,下有+1上不加;

while(left<right)
{
	int mid=left+(right-left)/2;
	if(...) left=mid+1;
	else right=mid;
}

3. 区间右值模板:

特点: 右值:右动,下有-1+1

while(left<right)
{
	int mid=left+(right-left+1)/2;
	if(...) right=mid-1;
	else left=mid;
}

题目1:704. 二分查找

【LeetCode刷题】专题三:二分查找模板-LMLPHP

思路分析:

【LeetCode刷题】专题三:二分查找模板-LMLPHP

思路1:朴素二分查找O(logN)

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)
                right = mid - 1;
            else if (nums[mid] < target)
                left = mid + 1;
            else
                return mid;
        }
        return -1;
    }
};

LeetCode链接:704. 二分查找


题目2:34. 在排序数组中查找元素的第一个和最后一个位置

【LeetCode刷题】专题三:二分查找模板-LMLPHP

思路分析:

本题请看代码注释:
主要三个点:判断条件、mid取值、left和right迭代
【LeetCode刷题】专题三:二分查找模板-LMLPHP

思路1:区间左右值二分查找 O(logN)

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int left=0,right=nums.size()-1;
        int begin=-1,end=-1;    
        if(nums.empty()) return {-1,-1}; 
        //1.区间左端点查找: 二分区间:[小于目标值][大于等于目标值] left维护前者,right维护后置,目标值在right区间左端取到。
        while(left<right)		//判断:为什么不能等于,因为最终结果是left=right处取到,=就死循环
        {
            int mid=left+(right-left)/2;	//当还剩最后left和right相邻时,指向左端点,结合迭代,左端点可以跳出来,右端点不能。
            if(nums[mid]>=target) right=mid;	//right不跳出区间,因为可能目标值就是right处
            else left=mid+1;					//left需要移动,因为目标值一定不在它的区间
        }
        if(target==nums[left])  begin=left;
        //2.区间左端点查找:  
        right=nums.size()-1;	//注意更新left和right,优化:右端点一定在左端点后,所以left可以不更新,就处于左端点处
        while(left<right)
        {
            int mid=left+(right-left+1)/2;	
            if(nums[mid]>target) right=mid-1;
            else left=mid;
        }
        if(target==nums[left])    end=left;
        
        return {begin,end};
    }
};

LeetCode刷题:34.在排序数组中查找元素的第一个和最后一个位置


进入二分,我更强大!!! ~天天开心🎈
【LeetCode刷题】专题三:二分查找模板-LMLPHP

05-31 22:34