文章目录
前言
算法作为极其重要的一点，是大学生毕业找工作的核心竞争力，所以为了不落后与人，开始刷力扣算法题！
第一遍，不求最优解，但求能过！！！
📢 博客主页：❤布小禅❤
📢 作者专栏：
这是我刷第 6/100 道力扣简单题
一、题目描述
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, …, n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
难度：简单
二、实例
输入：n = 5, bad = 4 输出：4 解释： 调用 isBadVersion(3) -> false 调用 isBadVersion(5) -> true 调用 isBadVersion(4) -> true 所以，4 是第一个错误的版本。
输入：n = 1, bad = 1 输出：1
三、题目解析
首先想到的肯定是暴力循环，一个一个遍历
遍历从1-n，符合要求立马停止循环，返回当前值
不过他题目要求是尽可能少的调用API
也就是说，暴力循环肯定是不行的
不过，我才管他行不行，我先试试暴力循环
毕竟我也只会暴力循环
# The isBadVersion API is already defined for you. # @param version, an integer # @return an integer # def isBadVersion(version): class Solution: def firstBadVersion(self, n): """ :type n: int :rtype: int """ ans = 0 # 设置一个变量接收答案 for i in range(n): if isBadVersion(i+1): # 因为i从0开始，到n-1结束 ans = i+1 break return ans
当我提交后，却出了红色，显示超出时间限制，也就是程序运行时间太长了
我不由得陷入了沉思，看来只能换个办法了，但是以我当前的知识储备好像也没别的方法了
我就瞄了一眼题解，发现需要使用二分查找法
3.1 二分查找法是什么
二分查找法是一种算法
他经常用在：
给定一个升序的数组/列表和一个目标值，尽可能快的查找其中的目标值
若存在，返回目标值得索引
若不存在，返回-1
这样的场景
因为是升序的，所以我们可以以数组中间的元素为中线，将数组分为左右两个数组
target = 7 # 给一个目标值 start = 0 # 用于计算中间值，和后面陆续的将数组划分为两个数组 end = len(li)-1 # 用于计算中间值，记录列表最后值的索引 li = [1, 2, 3, 4, 5, 6 ,7, 8, 9, 10] while start<n: # 记录一个循环 mid = (start+n)//2 # 值为4 """ 一个升序数组/列表 以中间mid（//是保持中间值为整数）为界限 看似分成两个数组 li_left = [1， 2， 3 ，4， 5] li_right = [6, 7, 8, 9, 10] """ if target>li[mid]: # 如果目标值比中间值大，就说名目标值（7）在右边的列表 start = mid+1 # 让start变成右边列表的第一个元素的索引 # 抛弃左边的列表不要，只看右边的列表li_right = [6, 7, 8, 9, 10] else: # 如果目标值小于等于中间值，就说明目标值在左边的列表 n = mid # 让n变成左边列表的最大值的索引 # 抛弃右边的列表不要，只看左边的列表
随着循环的进行，列表会越来越小，最后只剩目标值，然后最小值的索引start就是我们需要的值
3.2 将二分查找法应用在本题
因为我们有了一个接口可以判断哪个是错的，所以我们可以将bad看成目标值，将n（题干）看成列表的最大索引值n（实例代码），将isBadVerson()看成target>li[mid]
四、代码
# The isBadVersion API is already defined for you. # @param version, an integer # @return an integer # def isBadVersion(version): class Solution: def firstBadVersion(self, n): """ :type n: int :rtype: int """ start = 0 # 定义一个最小值索引 while start<n: # 循环 mid = int((start+n)/2) # 计算中间值的索引 if isBadVersion(mid): # 判断相当于target>li[mid] # 如果为True，就说明目标值（bad）在左边，相当于目标值比中间值大 n=mid else: start=mid+1 return start
结语
坚持最重要，每日一题必不可少！
