x 的平方根

二分法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
l = 1
h = x
while l <= h:
# 防止整数溢出
mid = l + (h - l) // 2
sqrt = x / mid
if sqrt == mid:
return mid
elif sqrt < mid:
h = mid - 1
else:
l = mid + 1
return h

寻找比目标字母大的最小字母

第一行的判断确保了在进入循环查询的letters最后面肯定是比target大的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
def nextGreatestLetter(self, letters, target):
"""
:type letters: List[str]
:type target: str
:rtype: str
"""
if target >= letters[-1]:
return letters[0]
lo = 0
hi = len(letters)
# a b c c c
while lo <= hi:
mid = lo + (hi - lo) // 2
if letters[mid] <= target:
lo = mid + 1
else:
hi = mid - 1
return letters[lo]

Single Element in a Sorted Array

主要是发现规律,因为有序,就会出现规律。规律就是在单个数字出现之前,偶数位和偶数位+1的数字是相等的,单个数字出现之后就不是这样了,因此可以通过此来判断是l往上增还是h往下降,所以算是二分法的一个变体,但是需要注意一些细节。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
def singleNonDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
# 主要是判断规律
l = 0
h = len(nums) - 1
while l < h:
mid = l + (h - l) // 2
# 要使得l, h都为偶数位
if mid % 2 == 1:
mid -= 1
if nums[mid] != nums[mid+1]:
h = mid
else:
l = mid + 2
return nums[l]

第一个错误的版本

标准的二分法,有几点需要注意:

  1. l < h 如果循环体中 h = mid 因为 h 和 l 可能相等,所以会导致没法退出循环的情况,所以
  2. h = mid 因为推导出解可能在 [l, m] 闭区间中,所以需要 h = mid
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
"""
l = 1
h = n
while l < h:
mid = l + (h - l) // 2
if isBadVersion(mid):
h = mid
else:
l = mid + 1
return l

寻找旋转排序数组中的最小值

当然可以使用min。。但是如果用二分法,就需要理解局部有序这一点,所以也就是二分法的变形罢了,需要注意些细节

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
# 局部有序
l = 0
h = len(nums) - 1
while l < h:
mid = l + (h - l) // 2
if nums[mid] <= nums[h]:
h = mid
else:
l = mid + 1
return nums[l]

搜索范围

先找到靠左的target元素,然后找到比这个元素大一的位置,减一就是target结尾的位置了。

主要是如何使用二分法找到左边key。因为 nums[m] >= target 中m也可能是解,所以 h = m

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
class Solution(object):
def binary_search(self, nums, key):
l = 0
h = len(nums)
while l < h:
mid = l + (h - l) // 2
if nums[mid] >= key:
h = mid
else:
l = mid + 1
return l
def searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
if not nums:
return [-1, -1]
start = self.binary_search(nums, target)
if start == len(nums) or nums[start] != target:
return [-1, -1]
else:
end = self.binary_search(nums, target + 1) - 1
return [start, end]

寻找重复数

比较绕,得多想一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
def findDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
# 可以使用二分查找,就是在确定mid的时候,
# 去判断下小于mid的数字有多少个
# 如果多于mid,则说明重复数字的值在mid左侧
# 如果少于等于mid,说明重复数字的值在mid右侧
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
cnt = len([n for n in nums if n <= mid])
if cnt > mid:
# 因为只要小于或者等于mid的总数多于mid,那么肯定是比mid小的数重复了
hi = mid - 1
else:
# 如果小于或者等于mid的总数小于或者等于mid,那么是
lo = mid + 1
return lo