力扣-第1天 二分查找

Source

力扣-14天算法入门

第1天 二分查找
第2天 双指针
第3天 双指针
第4天 双指针
第5天 双指针
第6天 滑动窗口
第7天 广度优先搜索 / 深度优先搜索
第8天 广度优先搜索 / 深度优先搜索
第9天 广度优先搜索 / 深度优先搜索
第10天 递归 / 回溯
第11天 递归 / 回溯
第12天 动态规划
第13天 位运算
第14天 位运算



前言

本系列文章是我的力扣刷题记录,采用c++进行编写


一、二分查找-查找一个数

难度(简单)
题目:给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。
分析:
根据题意这里是让我们找到 一个数组中的一个数,找到就返回该数在数组中的下标,数组中没有这个数就返回-1。
这是一个非常普遍的一个二分查找问题,我们只需要利用二分法对其逐步逼近就能得出。
具体步骤为:
我们先找出数组的左右区间,根据区间大小求出中间数的下标,然后只要中间数和目标数相等就返回该数下标,倘若中间数大于目标值,右边界左移,小于就另左边界右移。
具体代码如下:

class Solution {
    
      
public:
    int search(vector<int>& nums, int target) {
    
      

        int left = 0;
        int right = nums.size()-1;
        

        while (left <= right)
        {
    
      
            int mid =left + (right-left)/2;
            
            if (nums[mid] == target)
            {
    
      
                return mid;
            }
            else if(nums[mid] < target)
            {
    
      
                left = mid + 1;
            }
            else if(nums[mid] > target)
            {
    
      
                right = mid - 1;
            }      
                
        }
        return -1;
            
    }
};

二、二分查找-第一个错误的版本

难度(简单)
题目:你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, …, n],你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

示例 1:

输入:n = 5, bad = 4
输出:4
解释:
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以,4 是第一个错误的版本。

示例 2

输入:n = 1, bad = 1
输出:1

分析:
这一题和第一题大同小异,但这里要注意的是,当前版本是正确的话,后面的都是正确的。
我们对中间版本进行判断如果中间版本正确就令right = mid,否则就另left = mid+1。
具体代码如下:

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
    
      
public:
    int firstBadVersion(int n)
    {
    
      
        int left = 1;
        int right = n;
        while(left<right){
    
      
            int mid = left + (right - left) / 2;
            if (isBadVersion(mid))
            {
    
      
                right = mid;
            }
            else
            {
    
                     
                left = mid+1;
                    }
        }
        return left;
    }
};

三、二分查找-搜索插入位置

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

请必须使用时间复杂度为 O(log n) 的算法。

具体代码如下:

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


    }
};

总结

期待大家和我交流,留言或者私信,一起学习,一起进步!