算法思路：
- 循环条件start + 1 < end。 当跳出循环时，start和end的关系只能是相等或相邻。
相等是若数组只有一个元素，没有进入循环时出现。当进入过循环，一定是相邻。 - 跳出循环后比较start和end的关系从而判断答案。
这可以满足二分法找first position或者last position, peak element的题目。
first position中若等于target，end = mid，因为要在左半部分找，相反last
position在右半部分找，所以start = mid。
应用：
- 有序数组找目标
- 没给定目标情况下，找峰值， 缺失数(元素间关系)
- 没给定目标情况下，求第k小的数，如求根号（数值关系）
找目标
注意事项：
- 判断数组是否为空。
- 如果只有唯一的target的话，target==nums[mid]可以并入任何一种。end和target的顺序也没关系。其他注意循环后要根据题目条件(如小于或者大于或者等于tgt)，
再比较一次start和end上的元素，详见下表 - start + (end - start) // 2 是// 2
| 类型 | if target = nums[mid] | 循环之后 | 备注 |
|---|---|---|---|
| binary_search | 任意 | 任意 | N/A |
| last_position | 向右start = mid | 先end且是否等于tgt | 贪婪法，找最后一个target，所以尽量靠后，先end |
| first_position | 向左end = mid | 先start是否等于tgt | 贪婪法，找第一个target，所以尽量靠前，先start |
| smaller(_or_equal)_position | 向左end = mid | 先end是否小于tgt | 贪婪法，找最后一个小于target的数，所以尽量靠近target，先end |
| greater(_or_equal)_position | 向右start = mid | 先start是否大于tgt | 贪婪法，找第一个大于target的数，所以尽量靠近target，先start |
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17def binary_search(self, nums: List[int], target: int) -> int:
if not nums:
return -1
start, end = 0, len(nums) - 1
while start + 1 < end:
mid = start + (end - start) // 2
if target < nums[mid]:
end = mid
else:
start = mid
if nums[end] == target:
return end
elif nums[start] == target:
return start
else:
return -1
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19def last_position(self, nums: List[int], target: int) -> int:
if not nums:
return -1
start, end = 0, len(nums) - 1
while start + 1 < end:
mid = start + (end - start) // 2
if target < nums[mid]:
end = mid
elif target > nums[mid]:
start = mid
else: # Depends on the target on the right side or left side. For fist pos, use end = mid
start = mid
if nums[end] == target:
return end
elif nums[start] == target:
return start
else:
return -1
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19def first_position(self, nums: List[int], target: int) -> int:
if not nums:
return -1
start, end = 0, len(nums) - 1
while start + 1 < end:
mid = start + (end - start) // 2
if target < nums[mid]:
end = mid
elif target > nums[mid]:
start = mid
else:
end = mid
if nums[start] == target:
return start
elif nums[end] == target:
return end
else:
return -1
Python代码：
如果是smaller_or_equal_position，Line 13和15取等号
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17def smaller_position(self, nums: List[int], target: int) -> int:
if not nums:
return -1
start, end = 0, len(nums) - 1
while start + 1 < end:
mid = start + (end - start) // 2
if target > nums[mid]:
start = mid
elif target < nums[mid]:
end = mid
else:
end = mid
if nums[end] < target: # nums[end] <= target for smaller_or_equal_position
return end
if nums[start] < target: # nums[start] < target for smaller_or_equal_position
return start
return -1
Python代码：
如果是greater_or_equal_position，Line 13和15取等号
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17def greater_position(self, nums: List[int], target: int) -> int:
if not nums:
return -1
start, end = 0, len(nums) - 1
while start + 1 < end:
mid = start + (end - start) // 2
if target > nums[mid]:
start = mid
elif target < nums[mid]:
end = mid
else:
start = mid
if nums[start] > target: # nums[start] >= target for greater_or_equal_position
return start
if nums[end] > target: # nums[end] >= target for greater_or_equal_position
return end
return -1
找峰值
注意事项：
- 判断mid+1的元素不越界
- 最后返回start和end之中较大者
Python代码：
1
2
3
4
5
6
7
8
9
10
11def find_peak(self, nums: List[int]) -> int:
if not nums:
return -1
start, end = 0, len(nums) - 1
while start + 1 < end:
mid = start + (end - start) // 2
if mid + 1 <= end and nums[mid] < nums[mid + 1]:
start = mid
else:
end = mid
return start if nums[start] > nums[end] else end
数值二分法 - 找第k小的数
模板类似于标准二分法模板，区别是start和end取值以及epsilon取值是0.5而不是1
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12
13def minEatingSpeed(self, piles: List[int], target: int) -> int:
def f(piles, k):
return <按照题目要求>
start, end = <数值最小值>, <数值最小值>
while start + 0.5 < end:
mid = start + (end - start) / 2
res = f(piles, mid)
if <target与res的关系，需要在某一个条件取等号，以为是数值二分法>:
end = mid
else:
start = mid
return int(end)
注意事项：
- 思考数组范围(代码连续3行都是注意事项)
- epsilon取0.5. 一般整数题都取0.5
- mid是除2获得不是//2
- 模板中target和res取等号时，不能return，要继续在某半区找，因为要达到误差epsilon内才会停止。类似于first_position或者last_position
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15import math
def binary_select(self, nums: List[int], k: int) -> int:
if not nums:
return -1
start, end, epsilon = min(nums), max(nums), 0.5
while end - start > epsilon:
mid = start + (end - start) / 2
count = len([n for n in nums if n <= mid])
if k < count:
end = mid
elif k > count:
start = mid
else:
start = mid
return int(end)
上面line 8可以改成
1
count = bisect.bisect(matrix[i], mid)
注意事项：
- 数值比较，所以mid是除2获得不是//2。start，end，mid都是数值而不是索引
- k是从0开始，count==k的时候，k在mid的右边，如数组1-10, k=3, mid=3.5, count=3，k是前4个数，所以在mid右边。nums[i] <= mid这个等号有没有也没关系，因为mid是小数，不会相等的。
- 最后start，end区间内是一个整数正是所求，所以返回end向下取整
算法分析：
时间复杂度为O(nlog(|hi-lo|/epsilon))，如果数据比较平均也就是差值相当的情况下(比如1,2,3)，复杂度为O(nlogn). 空间复杂度O(1)。
若不需要搜索全数组，前面的n会变成logn
例子：
LeetCode 875 Koko Eating Bananas
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18def minEatingSpeed(self, piles: List[int], h: int) -> int:
#if len(piles) == 1: # attn
# return math.ceil(piles[0] / h)
# piles.sort()
def get_hours(piles, k):
return sum([math.ceil(n / k) for n in piles])
# start, end = piles[0], piles[-1] # 3, 4
start, end = 1, max(piles) # attn: 1 rather than min(piles)
while start + 0.5 < end: # attn: use 0.5
mid = start + (end - start) / 2 # attn /2 not // 2 | 7, 5, 4
hours = get_hours(piles, int(mid)) # attn: int(mid) | 5, 8, 8
if h >= hours: # eat slower, attn 8 > 5
end = mid # end=7, 5, 4
else:
start = mid
注意事项：
- start是从1开始，不是min(piles)。最大值取max(piles)因为跟取整型最大值是一样的。这样也可以避免单独处理单元素数组。
- epsilon取0.5. 一般整数题都取0.5
- mid是除2获得不是//2
- mid作为参数输入到get_hours()要去int(mid)与题目一致，因为题目的k是整数
- 模板中h==hours时，不能return，要继续在左半区找，因为要达到误差epsilon内才会停止。类似于first_position
如图所示，总体思路是左节点按层次遍历，而区别在于何时加入到结果集。