KK's blog

每天积累多一些

0%

Binary Search

Posted on Edited on Disqus:

算法思路：

  1. 循环条件start + 1 < end。 当跳出循环时，start和end的关系只能是相等或相邻。
    相等是若数组只有一个元素，没有进入循环时出现。当进入过循环，一定是相邻。
  2. 跳出循环后比较start和end的关系从而判断答案。

这可以满足二分法找first position或者last position, peak element的题目。
first position中若等于target，end = mid，因为要在左半部分找，相反last
position在右半部分找，所以start = mid。

应用：

  1. 有序数组找目标
  2. 没给定目标情况下，找峰值， 缺失数(元素间关系)
  3. 没给定目标情况下，求第k小的数，如求根号（数值关系）

找目标

注意事项：

  1. 判断数组是否为空。
  2. 如果只有唯一的target的话，target==nums[mid]可以并入任何一种。end和target的顺序也没关系。其他注意循环后要根据题目条件(如小于或者大于或者等于tgt)，
    再比较一次start和end上的元素，详见下表
  3. 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
17
def 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
19
def 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
19
def 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
17
def 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
17
def 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

找峰值

注意事项：

  1. 判断mid+1的元素不越界
  2. 最后返回start和end之中较大者

Python代码：

1
2
3
4
5
6
7
8
9
10
11
def 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
13
def 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)

注意事项：

  1. 思考数组范围(代码连续3行都是注意事项)
  2. epsilon取0.5. 一般整数题都取0.5
  3. mid是除2获得不是//2
  4. 模板中target和res取等号时，不能return，要继续在某半区找，因为要达到误差epsilon内才会停止。类似于first_position或者last_position

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import 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)

若nums有序，count的统计可以用bisect(nums, mid)完成，记得不需要用+1，而且空数组也无问题
上面line 8可以改成

1
count = bisect.bisect(matrix[i], mid)

注意事项：

  1. 数值比较，所以mid是除2获得不是//2。start，end，mid都是数值而不是索引
  2. k是从0开始，count==k的时候，k在mid的右边，如数组1-10, k=3, mid=3.5, count=3，k是前4个数，所以在mid右边。nums[i] <= mid这个等号有没有也没关系，因为mid是小数，不会相等的。
  3. 最后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
18
def 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

注意事项：

  1. start是从1开始，不是min(piles)。最大值取max(piles)因为跟取整型最大值是一样的。这样也可以避免单独处理单元素数组。
  2. epsilon取0.5. 一般整数题都取0.5
  3. mid是除2获得不是//2
  4. mid作为参数输入到get_hours()要去int(mid)与题目一致，因为题目的k是整数
  5. 模板中h==hours时，不能return，要继续在左半区找，因为要达到误差epsilon内才会停止。类似于first_position
Free mock interview