【LeetCode刷题】专题三：二分查找模板

【LeetCode刷题】Day 11

• 专题三：二分查找模板：
• • 1. 朴素二分模板：
  • 2. 区间左值模板：
  • 3. 区间右值模板：
• 题目1：704. 二分查找
• • 思路分析：
  • 思路1：朴素二分查找O(logN)
• 题目2：34. 在排序数组中查找元素的第一个和最后一个位置
• • 思路分析：
  • 思路1：区间左右值二分查找 O(logN)

专题三：二分查找模板：

根据题干分析，根据二分性，划分区间，得出二分最重要的几个要点：

1. 判断条件：while(......) 是left<=right 还是left<right。这是第一个容易死循环的点。

2. 求中点的方式：mid = left + (right-left)/2 还是 mid = left + (right-left+1)/2这个点很关键。如果和下面mid的迭代不相符，这便是第二个死循环的点。

3. 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. 二分查找

思路分析：

思路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. 在排序数组中查找元素的第一个和最后一个位置

思路分析：

本题请看代码注释：

主要三个点：判断条件、mid取值、left和right迭代

思路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.在排序数组中查找元素的第一个和最后一个位置

进入二分，我更强大！！！ ~天天开心