Binary Search 总结
$ T(n) = T(\frac {n}{2}) + O(1) = O(logn)$
如果需要优化 O(n) 的时间复杂度,一般只能是 O(logn) 的二分法
四点要素:
start + 1 < end 这样就不用考虑两个指针的前后,最后结束时一定是相邻的
start + (end - start) / 2 虽然对python来说不重要,但是对于Java等可以防止溢出
A[mid] ==, <, > 这个会根据题目的不同来调整
A[start] A[end] ? target
针对Sorted数组查找的算法
时间复杂度: O(log(n))
二分查找法的前置条件要拥有一个已经Sorted好的序列,这样在查找所要查找的元素时, 首先与序列中间的元素进行比较, 如果大于这个元素, 就在当前序列的后半部分继续查找, 如果小于这个元素, 就在当前序列的前半部分继续查找, 直到找到相同的元素, 或者所查找的序列范围为空为止.
left = 0, right = n -1
while (left <= right)
mid = (left + right) / 2
case
x[mid] < t: left = mid + 1;
x[mid] = t: p = mid; break;
x[mid] > t: right = mid -1;
return -1;
溢出
mid = (l+r)//2
在对两个Signed 32-bit数字进行相加时,有可能出现溢出,例如下面这种情况:
left = 1, right = Integer.MAX_VALUE
当left 与 right 之和超过了所在类型的表示范围的话, 这个和就会成为一个很随机的值, 那么 middle 就不会得到正确的值.
所以, 更稳妥的做法应该是这样的:
mid = l + (r-l)//2
边界错误
二分查找算法的边界, 一般来说分两种情况:
- 左闭右开区间, 类似于 [left, right)
- 左闭右闭区间, 类似于 [left, right]
死循环
模板选择
case 1 (问题占多数):
def binarySearch(arr, target):
l , r = 0, len(arr) - 1
while l <= r:
mid = (l+r)//2
if arr[mid] == target:
return mid
if target > arr[mid]:
l = mid + 1
else:
r = mid - 1
return -1
case 2 (问题占少数):
def binary_search(array, target):
start, end = 0, len(array) - 1
while start + 1 < end:
mid = (start + end) / 2
if array[mid] == target:
start = mid
elif array[mid] < target:
start = mid
else:
end = mid
if array[start] == target:
return start
if array[end] == target:
return end
return -1
题目分类
题目类型分为三类:
- 有明确Target
- 没有明确Target
- 没有明确Target (可越界类型)
leetcode binary search problems
请多多指教。
文章标题:Binary Search 总结
本文作者:顺强
发布时间:2020-04-13, 23:59:00
原始链接:http://shunqiang.ml/leetcode-binary-search-summary/版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。