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上的元素，详见下表
类型 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小的数

注意事项：

  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向下取整

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)

算法分析：

时间复杂度为O(nlog(|hi-lo|/delta))，如果数据比较平均也就是差值相当的情况下(比如1,2,3)，复杂度为O(nlogn). 空间复杂度O(1)。
若不需要搜索全数组，前面的n会变成logn

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int lastPosition(int[] nums, int target) {
	if(nums == null || nums.length == 0)
		return -1;
	
	int start = 0, end = nums.length - 1;
	while(start + 1 < end) {
		int mid = start + (end - start) / 2;
		if(nums[mid] < target)
			start = mid;
		else if(nums[mid] == target) 
		// Depends on the target on the right side or left side. For fist pos, use end = mid
			start = mid; 
		else
			end = mid;
	}
	
	if(nums[end] == target)
		return end;
	if(nums[start] == target)
		return start;
	
	return -1;
}

算法分析：

时间复杂度为O(logn)，空间复杂度O(1)。

Free mock interview