刷题训练之二分查找

简介: 本文详细介绍了二分查找算法,包括其时间复杂度、适用场景(如有序/无序数组),并提供了针对LeetCode上常见题型的解析,包括查找、范围搜索和插入位置等,强调理解和记忆关键模板。

> 作者:დ旧言~

> 座右铭:松树千年终是朽,槿花一日自为荣。

> 目标:熟练掌握二分查找算法

> 毒鸡汤:学习,学习,再学习 ! 学,然后知不足。

> 专栏选自:刷题训练营

> 望小伙伴们点赞👍收藏✨加关注哟💕💕



🌟前言分析

       最早博主续写了牛客网130道题,这块的刷题是让同学们快速进入C语言,而我们学习c++已经有一段时间了,知识储备已经足够了但缺少了实战,面对这块短板博主续写刷题训练,针对性学习,把相似的题目归类,系统的刷题,而我们刷题的官网可以参考:


而今天我们的板块是二分查找。


⭐知识讲解

很多小伙伴们在想二分查找嘛,只有升序或者是降序的数字里面查找,有这个想法的是大错特错的,在一些题目中有些无序也可以使用二分查找,所以说二分查找的知识点没有我们想的那么简单,在二分查找中我们会总结一些模板,这些模板要死记硬背要理解哦,题目选取的很多,大家不要跳过一些题目,有些题目是为后面的题目做铺垫的,望大家可以从头看到尾,这里就简单的总结一些二分查找的知识点:


  • 二分查找的时间复杂度:log(N)
  • 二分查找的范围:有序的数组或者无序


⭐经典题型

🌙topic-->1

题目链接:



题目分析:

在一个有序的数组中查找一个数字  target  ,如果存在就返回数组的下标,没有的话就返回-1

算法原理:

  • 解法一:

暴力遍历数组,时间复杂度为O(n)。

  • 解法二:

采用二分查找,二分算法原理博客,这里如果不会二分查找的小伙伴们大家可以看看这篇博客,这里我们再讲解一下解法二的算法原理。

图解:



细节:

  1. 防止 mid 超过整形最大值
  2. 循环的条件是 left <= right

代码演示:

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


模板总结:

 
        // 定义左右指针
        int left = 0,right = nums.size() - 1;
        // 循环
        while(left <= right) // 细节二
        {
            // int mid = left + (right - left + 1) / 2 等价
            int mid = left + (right - left) / 2;// 细节一
            if(....)
                left = mid + 1;
            else if(....)
                right = mid - 1;
            else
                return ...;
        }


🌙topic-->2

题目链接:



题目分析:

在一个非递归中找一个等于 target 下标,如果没有就返回 {-1,-1}

算法原理:

  • 解法一:

暴力遍历数组,时间复杂度为O(n)。

  • 解法二:

采用二分查找,二分算法原理博客,这里如果不会二分查找的小伙伴们大家可以看看这篇博客,这里我们再讲解一下解法二的算法原理。


代码演示:

class Solution
{
public:
  vector<int> searchRange(vector<int>& nums, int target)
  {
        // 定义左右指针
        int left = 0,right = nums.size() - 1;
        // 处理空数组
        if(nums.size() == 0)
            return {-1,-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)
            return {-1,-1};
        else 
            begin = left;//标记左边界
        // 去除右边界
        left = 0,right = nums.size() - 1;
        while(left < right)
        {
            int mid = left + (right - left + 1) / 2; // 细节
            if(nums[mid] <= 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;
}
 
while(left < right)
{
    int mid = left + (right - left + 1) / 2;
    if(...) left = mid;
    else right = mid - 1;
}
 
// 下面出现 -1 的时候,上面就加 +1


🌙topic-->3

这道题目就不再讲解的这么细了,具体还得琢磨第二道题目:

题目链接:



题目分析:

给定一个排序数

给定一个排序数组(升序)和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

算法原理:

  • 解法一:

暴力遍历数组,时间复杂度为O(n)。

  • 解法二:

采用二分查找,二分算法原理博客,这里如果不会二分查找的小伙伴们大家可以看看这篇博客,这里我们再讲解一下解法二的算法原理。

代码演示:

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


🌙topic-->4

这道题目就不再讲解的这么细了,具体还得琢磨第二道题目:

题目链接:



题目分析:

求 X 的算数平方根,结果保留整数。

算法原理:

  • 解法一:

暴力举例1 2 3 .... x,时间复杂度为O(n)。

  • 解法二:

采用二分查找,二分算法原理博客,这里如果不会二分查找的小伙伴们大家可以看看这篇博客,这里我们再讲解一下解法二的算法原理。

代码演示:

class Solution {
public:
    int mySqrt(int x) 
    {
        // 处理
        if(x < 1) return 0;
        // 定义两个指针
        int left = 1,right = x;
        // 循环
        while(left <right)
        {
            // 防止溢出
            long long mid = left + (right - left +1) /2;
            if(mid * mid <= x) left = mid;
            else right = mid -1;
        }
        return left;
    }
};


 

 🌙topic-->5

这道题目就不再讲解的这么细了,具体还得琢磨第二道题目:

题目链接:


 


题目分析:

有一个山峰数组(数组有递增和递减),返回数组中峰顶的下标。

算法原理:

  • 解法一:

暴力遍历数组就可以了,时间复杂度为O(n)。

  • 解法二:

采用二分查找,二分算法原理博客,这里如果不会二分查找的小伙伴们大家可以看看这篇博客,这里我们再讲解一下解法二的算法原理。



代码演示:

class Solution {
public:
    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;
    }
};


 

 🌙topic-->6

这道题目就不再讲解的这么细了,这里和第五道题目几乎一样:

题目链接:


 


题目分析:

有一个山峰数组,这个山峰数组有多个山峰,只要返回其中一峰顶就行(返回数组中峰顶的下标)

算法原理:

  • 解法一:

暴力遍历数组就可以了,时间复杂度为O(n)。

  • 解法二:

采用二分查找,二分算法原理博客,这里如果不会二分查找的小伙伴们大家可以看看这篇博客,这里我们再讲解一下解法二的算法原理。

代码演示:

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


🌙topic-->7

这道题目就不再讲解的这么细了,具体还得琢磨第二道题目:

题目链接:


 


题目分析:

在一个数组中找最小值。

算法原理:

  • 解法一:

暴力遍历数组就可以了,时间复杂度为O(n)。

  • 解法二:

采用二分查找,二分算法原理博客,这里如果不会二分查找的小伙伴们大家可以看看这篇博客,这里我们再讲解一下解法二的算法原理。



代码演示:

class Solution
{
public:
  int findMin(vector<int>& nums)
  {
    int left = 0, right = nums.size() - 1;
    int x = nums[right]; // 标记⼀下最后⼀个位置的值
    while (left < right)
    {
      int mid = left + (right - left) / 2;
      if (nums[mid] > x) left = mid + 1;
      else right = mid;
    }
    return nums[left];
  }
};


🌙topic-->8

这道题目就不再讲解的这么细了,具体还得琢磨第二道题目:

题目链接:


 


题目分析:

在一个  0 ~  n-1  数组中找缺少的数字。

算法原理:

  • 解法一:

暴力遍历数组就可以了,时间复杂度为O(n)。

  • 解法二:

采用二分查找,二分算法原理博客,这里如果不会二分查找的小伙伴们大家可以看看这篇博客,这里我们再讲解一下解法二的算法原理。



代码演示:

class Solution {
public:
    int takeAttendance(vector<int>& records) {
        int missingNumber(vector<int>&nums)
        {
            int left = 0, right = nums.size() - 1;
            while (left < right)
            {
                int mid = left + (right - left) / 2;
                if (nums[mid] == mid) left = mid + 1;
                else right = mid;
            }
            return left == nums[left] ? left + 1 : left;
        }
    }
};


🌟结束语

      今天内容就到这里啦,时间过得很快,大家沉下心来好好学习,会有一定的收获的,大家多多坚持,嘻嘻,成功路上注定孤独,因为坚持的人不多。那请大家举起自己的小手给博主一键三连,有你们的支持是我最大的动力💞💞💞,回见。


目录
相关文章
|
4月前
|
算法 C语言 C++
刷题训练之前缀和(上)
本文围绕前缀和算法展开,介绍了C++实现的多种经典题型,包括一维和二维前缀和,以及中心下标和子数组和等问题,强调实战学习的重要性,鼓励读者通过刷题提升技能。
46 0
刷题训练之前缀和(上)
|
4月前
|
算法 Java C语言
刷题训练之双指针问题
刷题训练之双指针问题
30 0
|
4月前
|
算法 搜索推荐 C语言
刷题训练之分治快排
刷题训练之分治快排
21 0
|
4月前
|
算法 C语言 C++
刷题训练之分治归并
刷题训练之分治归并
22 0
|
4月前
|
机器学习/深度学习 算法 C++
刷题训练之前缀和(下)
本文围绕前缀和算法展开,介绍了C++实现的多种经典题型,包括一维和二维前缀和,以及中心下标和子数组和等问题,强调实战学习的重要性,鼓励读者通过刷题提升技能。
42 0
|
5月前
|
算法 JavaScript 前端开发
算法学习:二分查找
算法学习:二分查找
56 0
|
6月前
|
算法
|
算法 C++
C++基础算法二分篇
C++基础算法二分篇
|
算法
算法设计与分析/数据结构与算法实验6:0-1背包问题(回溯法)
算法设计与分析/数据结构与算法实验6:0-1背包问题(回溯法)
209 0
算法设计与分析/数据结构与算法实验6:0-1背包问题(回溯法)