力扣每日一练之二分查找Day7

🍕前面的话🥞

大家好！本篇文章将介绍20天算法刷题计划的题，本文将以三道题作为背景，介绍经典的二分查找，展示语言为java（博主学习语言为java)。今天呢，是博主开始刷力扣的第五天，如果有想要开始准备自己的算法面试的同学，可以跟着我的脚步一起，共同进步。大家都是并肩作战的伙伴，一起努力奋力前行，路漫漫其修远兮，吾将上下而求索，相信我们一定都可以拿到自己期望的offer，冲冲冲！

👩‍💻博客主页：京与旧铺的博客主页

✨欢迎关注🖱点赞🎀收藏⭐留言✒

🔮本文由京与旧铺原创，csdn首发！

😘系列专栏：java学习

💻首发时间：🎞2022年5月11日🎠

🎨你做三四月的事，八九月就会有答案，一起加油吧

🔏参考在线编程网站：🎧力扣

🀄如果觉得博主的文章还不错的话，请三连支持一下博主哦

🎧最后的话，作者是一个新人，在很多方面还做的不好，欢迎大佬指正，一起学习哦，冲冲冲

🏓导航小助手📻

图片

🎀Leetcode704.二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

 示例 1:
 ​
 输入: nums = [-1,0,3,5,9,12], target = 9
 输出: 4
 解释: 9 出现在 nums 中并且下标为 4
 示例 2:
 ​
 输入: nums = [-1,0,3,5,9,12], target = 2
 输出: -1
 解释: 2 不存在 nums 中因此返回 -1
 ​
 ​

🎏源代码

 class Solution {
     public int search(int[] nums, int target) {
         int low=0,high=nums.length-1;
         while(low<=high){
             int mid=(high-low)/2+low;
             int num=nums[mid];
             if(num==target){
                 return mid;
             }else if(num<target){
                 low=mid+1;
             }else{
                 high=mid-1;
             }
         }
         return -1;
     }
 }

🧶解题思路

设定左右指针 找出中间位置，并判断该位置值是否等于 target nums[mid] == target 则返回该位置下标 nums[mid] > target 则右侧指针移到中间 nums[mid] < target 则左侧指针移到中间

🎡LeetCode278.第一个错误的版本

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

假设你有 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

🎑源代码

 /* The isBadVersion API is defined in the parent class VersionControl.
       boolean isBadVersion(int version); */
 ​
 public class Solution extends VersionControl {
     public int firstBadVersion(int n) {
         int left=1,right=n;
         while(left<right){
             int mid=left+(right-left)/2;
             if(isBadVersion(mid)){
                 right=mid;
             }else{
                 left=mid+1;
             }
             
         }
         return left;
     }
 }

🎎解题思路

因为题目要求尽量减少调用检查接口的次数，所以不能对每个版本都调用检查接口，而是应该将调用检查接口的次数降到最低。

注意到一个性质：当一个版本为正确版本，则该版本之前的所有版本均为正确版本；当一个版本为错误版本，则该版本之后的所有版本均为错误版本。我们可以利用这个性质进行二分查找。

具体地，将左右边界分别初始化为 11 和 nn，其中 nn 是给定的版本数量。设定左右边界之后，每次我们都依据左右边界找到其中间的版本，检查其是否为正确版本。如果该版本为正确版本，那么第一个错误的版本必然位于该版本的右侧，我们缩紧左边界；否则第一个错误的版本必然位于该版本及该版本的左侧，我们缩紧右边界。

这样我们每判断一次都可以缩紧一次边界，而每次缩紧时两边界距离将变为原来的一半，因此我们至多只需要缩紧 O(\log n)O(logn) 次。

🧥Leetcode35.搜索输入位置

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

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

 示例 1:
 ​
 输入: nums = [1,3,5,6], target = 5
 输出: 2
 示例 2:
 ​
 输入: nums = [1,3,5,6], target = 2
 输出: 1
 示例 3:
 ​
 输入: nums = [1,3,5,6], target = 7
 输出: 4

👠源代码

 class Solution {
     public int searchInsert(int[] nums, int target) {
          int left=0,right=nums.length-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{
                  right=mid-1;
              }
          }
          return left;
     }
 }

🥾解题思路

如果该题目暴力解决的话需要 O(n)O(n) 的时间复杂度，但是如果二分的话则可以降低到 O(logn)O(logn) 的时间复杂度 整体思路和普通的二分查找几乎没有区别，先设定左侧下标 left 和右侧下标 right，再计算中间下标 mid 每次根据 nums[mid] 和 target 之间的大小进行判断，相等则直接返回下标，nums[mid] < target 则 left 右移，nums[mid] > target 则 right 左移 查找结束如果没有相等值则返回 left，该值为插入位置 时间复杂度：O(logn)O(logn)

🌌总结

通过这三道题，我们学习了二分查找，复习了数组和循环的知识，那么呢，期待一下下一篇文章吧，和我一起进步，每天努力多一些，迈出更大的一步

觉得文章写的不错的亲亲，点赞评论关注走一波，爱你们哦🛴