Binary Search - Githubissues

主要题型

给定数组，寻找某个数第一次出现/第n次出现/最后一次出现的下标

时间复杂度

O(1) 极少
O(logn) 几乎都是二分法
如果通过O(n)遍历即可得出的，一般都会存在O（logn）的优化方案
O(√n) 几乎是分解质因数
O(n) 高频
O(nlogn) 一般都可能要排序
O(n^2) 数组，枚举，动态规划
O(n^3) 数组，枚举，动态规划
O(2n) 与组合有关的搜索
O(n!) 与排列有关的搜索 根据时间复杂度，倒推可能的算法，也是一种构建算法的思路！

Recursion or While loop？

面试中是否使用 Recursion 的几个判断条件

面试官是否要求了不使用 Recursion （如果你不确定，就向面试官询问）
不用 Recursion 是否会造成实现变得很复杂
Recursion 的深度是否会很深
题目的考点是 Recursion vs Non-Recursion 还是就是考你是否会Recursion？

递归的危险：StackOverflow，内存消耗极大 记住：不要自己下判断，要跟面试官讨论！

Binary Search 的常见痛点

循环结束条件到底是哪个？
1. start <= end
2. start < end
3. start + 1 < end
指针变化到底是哪个？
1. start = mid
2. start = mid + 1
3. start = mid - 1

mid = start + (end - start)/2 相较于 mid = (start + end)/2的优势在于，如果start和end过大，有可能造成越界。 while（start < end） 的结束条件是start == end, 而start + 1 < end则为两个指针相邻时结束，可以有效避免死循环。

while(start < end):
    mid = int(start + (end - start)/2)
    if a[mid] == target:
        start = mid # 因为要找最后一个出现，若start=mid+1，当mid为最后一次时，就会漏检
    elif a[mid] < target:
        start = mid # or start = mid + 1
    else:
        end = mid # or end = mid - 1

因为mid偏左，如果a[mid] == target, start = mid时，有可能一轮检测下来，start不会发生移动例如寻找[1,1]中最后一次1出现的位置时，mid = start = 0，start停留在原地解决思路就是修改循环结束的判断条件，将start < end改为start + 1< end

关键点总结

start + 1 < end避免死循环
mid = start + (end - start)/2避免内存越界
<,==,>三种情况分类讨论，即使有可能存在<=,>=为一类处理模式，但是分开讨论可以避免细节错误
循环结束时，判断返回值为start还是end

BS直观题目：寻找满足条件的的第一个/最后一个位置

1. 寻找ooooo_ox_xxxxxx

最直观的BS，如果找到的mid = o，则在右侧，如果找到的是x，则为当前位置或者左侧
2. 特别类型：如果数组长度特别长，无法获得终点的长度，如何实现BS寻找目标？时间复杂度如何分析？
从起点0开始，利用倍增的思想，每次count = count * 2跳跃式前进
若目标index = k，则在log（k）次即可保证count落在（k，2k）的区间内，即（count/2， count）内存在k
之后再次利用朴素BS思想，在（count，count*2）区间内，寻找目标k
时间复杂度为倍增+BS的结合，即log（k）+ log（0.5count）想加，为O（log（k））
3. Rotated Sorted Array
核心目标：寻找反转点，即rotate之后最小值的index
利用BS进行寻找：将前序构成oo，后序构成xx，寻找交界点
mid应该与什么值进行比较？与a[0] or a[-1]？
- 考虑特殊情况：没有rotate，即正常的sorted array，若与a[0]做判断则无法进行

BS非直观题目（half half）：无法轻易找到ooxx条件进行二分判断

二分的本质思考：利用一次判断，缩小一半搜索的内容

例题：
- Maximum Number in Mountain Sequence
- Find Peak Element
  - 如果需要寻找所有的peak，只能遍历之后确定结果，时间复杂度 >= O(n)
  - 如果只是寻找一个peak，则可以利用BS的二分思想进行优化，终极目标为时间复杂度 = O(logn)
  - 思路：先判断mid出现的坡段，即增长区间/峰值（直接return）/下降区间/波谷（左右都可）
  - 增区间：右侧一定能有peak，调整start
  - 减区间：左侧一定有peak，调整end
  - 特别注意：若最小/最大值不止一个，唯一可行结果就是遍历O(n)，无法利用BS进行优化
- Search in Sorted Array
  - 思路1: 还原成sorted array，但是还原这个步骤就需O(n)的时间复杂度，不如直接遍历
  - 思路2: 虽然rotate了，但是核心还是一个sorted array，即可以通过判断区间来确认目标值在左还是右
  - 第一层判断：通过mid >= start或mid <= a[-1]可以确认mid在前序还是后序序列
  - 第二层判断：确定mid 和target的大小关系，进而缩小搜索区间
```
def search(self, nums: List[int], target: int) -> int:
start = 0
end = len(nums)-1
while start <= end:
    mid = start + (end - start)//2
    if nums[mid] == target:
        return mid
    if nums[mid] >= nums[start]: # mid is at the prev part
        if target >= nums[start] and nums[mid] >= target: # start <= target <= mid
            end = mid
        else:
            start = mid + 1 
            # mid is on the left, so if not + 1, some times the mid == start and cause infinite loop
    else:
        if target <= nums[end] and nums[mid] <= target:
            start = mid + 1
        else:
            end = mid
return -1
```

LC.981

有助于理解，mid的取值与逼近方向的联系

具体判断寻找oooxxx中最后一次出现的o还是第一次出现的x

mid = (start + end + 1)//2: mid偏右侧，若a[mid] > target 则end = mid - 1

用以寻找ox中o出现的位置，通过右侧向左逼近，从而保证最终收敛与o上，而不是x上
同时最重要的是，可以避免mid = o时，start = mid + 1跳过符合条件的值

mid = (start + end)//2: mid偏左侧，若a[mid] < target 则start = mid + 1

mid偏左，则需要左侧向右侧逼近，而不会漏检ooxx中第一个出现的x

while start < end:
mid = (start + end + 1)//2 # 需要找第一个小于的值，所以希望调整end的位置来向左逼近
# mid偏右，每次需要调整end左移，而start = mid可以保证不会跳过小于目标的值
# 最终通过右侧逼近的方式，可以收敛在第一个小于等于target的index上
value, prev_stamp = alist[mid]
if prev_stamp > timestamp:
end = mid - 1 # 右边界向左收敛
else:
start = mid # a[mid] <= target，若mid+1则有可能跳过最后一个符合条件的最大值
# 为了start = mid不会停留在原地不更新，决定了mid = （start+end+1）/2 ，否则会infinite loop
return alist[start][0] if alist[start][1] <= timestamp else ''

LC.240 Search a 2D Matrix II

Solution1: BS in each row and col

由于矩阵特性，可以从左上角开始确定起点，每次沿着col和row进行BS 搜索，当扫描起点从左上移动至底部，即可完成对矩阵的一次遍历

在每一行和每一列进行搜索时，可以利用BS来优化，因为此时即为一般的一维Sorted Array

时间复杂度： O(logn)+O(log(n-1)) + ... + O(log1)

= O(log(n*(n-1)*(n-2)**(1))) = O(log(n!)) <= O(nlogn) = O(logn^n)


def search(self,matrix, target, start, horizon):
low = start
high = len(matrix[0])-1 if horizon else len(matrix) - 1
# we don't need to find the index, all we care is the existence
# if we found than return Ture
# otherwise, we keep BS until the low>high to make sure that we didn't miss anything
while low <= high:
    mid = low + (high - low)//2
    if horizon:
        if matrix[start][mid] < target:
            low = mid + 1
        elif matrix[start][mid] > target:
            high = mid - 1
        else:
            return True
    else:
        if matrix[mid][start] < target:
            low = mid + 1
        elif matrix[mid][start] > target:
            high = mid - 1
        else:
            return True
return False

def searchMatrix(self, matrix, target): """ :type matrix: List[List[int]] :type target: int :rtype: bool """ if not matrix: return False

start from the top left[0][0], iterate through [x][x] until reach the bottom O(min(n,m))

# each time, from [start][start], we use BS to search inside the row and col O(log(len-start)) # the whole time complexity is O(logn)+O(log(n-1)) + ... + O(log1) # T = O(log(n*(n-1)*(n-2)**(1))) = O(log(n!)) <= O(nlogn) = O(logn^n) for i in range(min(len(matrix), len(matrix[0]))): horizonResult = self.search(matrix, target, i, True) verticalResult = self.search(matrix, target, i, False) if horizonResult or verticalResult: return True return False

#### Solution2: Divide and Conquer - DC涉及到递归**Recursion**，所以当矩阵规模很大时，**容易内存溢出**，所以尽量避免使用Recursion - 因为矩阵有序，所以如果确定了其中一个值，那么左上角的矩阵元素都比他小，右下角的有比他大 - 利用这个特性，确定中间一列为`mid = (left + right)//2`，之后遍历`row from top to bottom` - 当`matrix[row−1][mid] < target < matrix[row][mid]`的时候，即可排除左上角和右下角的两个矩阵 - 在左下和右上两个子矩阵内继续搜索，直到`subMatrix[row][mid] == target`，否则矩阵内不存在`target` - **Time complexity : O(nlgn)** ```Python def searchMatrix(self, matrix, target): # an empty matrix obviously does not contain `target` if not matrix: return False def search_rec(left, up, right, down): # this submatrix has no height or no width. if left > right or up > down: return False # `target` is already larger than the largest element or smaller # than the smallest element in this submatrix. elif target < matrix[up][left] or target > matrix[down][right]: return False mid = left + (right-left)//2 # Locate `row` such that matrix[row-1][mid] < target < matrix[row][mid] row = up while row <= down and matrix[row][mid] <= target: if matrix[row][mid] == target: return True row += 1 return search_rec(left, row, mid-1, down) or search_rec(mid+1, up, right, row-1) return search_rec(0, 0, len(matrix[0])-1, len(matrix)-1)

Solution3: Search Space Reduction（best soluion）

因为矩阵的特性，若从左下角开始寻找，如果target > matrix[row][col]则只需要向右侧移动一格，如果target < matrix[row][col]则只能向上移动

从左下开始时，大于的值只存在右侧，小于的只存在上方

同理，从右上开始时，大于的只在下方，小于的只在左侧

若从左上和右下开始，则大于或者小于有两个方向可以选择，无法确认路径的唯一性

时间复杂度，由于最坏情况为一直走到右上角，所以总路径长度为m+n，即O(m+n)

def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
if len(matrix) == 0 or len(matrix[0]) == 0:
    return False
width = len(matrix[0])
height = len(matrix)

row = height - 1
col = 0
while col < width and row >= 0:
    if target == matrix[row][col]:
        return True
    elif target > matrix[row][col]:
        col += 1
    else:
        row -= 1
return False

junhong7 / Algorithm

Binary Search #3