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

简介: 【LeetCode刷题】专题三:二分查找模板

专题三:二分查找模板:

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

  1. 判断条件:while(......) 是left<=right 还是left
  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.在排序数组中查找元素的第一个和最后一个位置

相关文章
|
1月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
1月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
1月前
|
索引
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
|
1月前
|
算法
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
|
1月前
|
算法 容器
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
|
1月前
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积
|
1月前
【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名
【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名
|
1月前
【LeetCode刷题】滑动窗口思想解决:最大连续1的个数 III、将x减到0的最小操作数
【LeetCode刷题】滑动窗口思想解决:最大连续1的个数 III、将x减到0的最小操作数
|
1月前
【LeetCode刷题】滑动窗口思想解决问题:长度最小的子数组、无重复字符的最长子串
【LeetCode刷题】滑动窗口思想解决问题:长度最小的子数组、无重复字符的最长子串
|
1月前
|
算法 容器
【LeetCode刷题】三数之和、四数之和
【LeetCode刷题】三数之和、四数之和