278. 第一个错误的版本(Easy)
# 题解
明确目标,找出错误的版本,当找到错误版本的时候 right = mid
,可以接受。当找到正确版本的时候,需要拒绝left = mid + 1
二分查找实现的四个条件
- 向左查找:left = mid + 1
- **向右查找:right = mid **
# 题解
二分查找
明确一点:寻找到的值是靠右的
# Python示例
# 模板1 左闭右闭
class Solution:
def firstBadVersion(self, n):
"""
:type n: int
:rtype: int
"""
ans = 0
left, right = 1, n
while left <= right:
mid = (left + right) >> 1
is_bad_version = isBadVersion(mid)
if is_bad_version == True:
ans = mid # 这里一定是 mid, ans 一定是在 is_bad_version 为 True 的情况
right = mid - 1
else:
left = mid + 1
return ans
# 模板2 左闭右开,自然是找到靠右的值
class Solution:
def firstBadVersion(self, n):
"""
:type n: int
:rtype: int
"""
left, right = 1, n + 1 # 开区间
while left < right:
mid = (left + right) >> 1
is_bad_version = isBadVersion(mid)
if is_bad_version == True:
right = mid
else:
left = mid + 1
return left
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
编辑 (opens new window)
上次更新: 2022/10/25, 02:40:54