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