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

🍕前面的话🥞

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

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

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

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

😘系列专栏：java 学习

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

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

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

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

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

🏓导航小助手📻

[TOC]

图片

🎀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;    }}

🧶解题思路

设定左右指针找出中间位置，并判断该位置值是否等于 targetnums[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)

🌌总结

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

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