Leetcode-278-第一个错误的版本

发表于 | 分类于 ，

二分查找的初级应用

img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
\# The isBadVersion API is already defined for you.
\# @param version, an integer
\# @return a bool
\# def isBadVersion(version):

class Solution(object):
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """

        start, end = 1, n 
        while start < end:
            middle = int((start+end)/2)
            if isBadVersion(middle):
                end = middle
            else:
                start = middle + 1
        return start

本题主要运用了二分查找的只是，创建start和end作为开始和结束的标记，每次取middle值作为判断的依据，由于题中所给序列可以看成是一个有序数列，因此如果middle大于给定值 即isBadVersion==True，则把end标记置为middle，否则把start置为 middle+1

是是