二分查找

实质：不断地将有序数据集进行对半分割，并检查每个分区的中间元素

二分搜索（折半搜索）是一种在有序数组中查找某一特定元素的搜索算法。从定义可知，运用二分搜索的前提是数组必须是排好序的。另外，输入并不一定是数组，也有可能是给定一个区间的起始和终止的位置。
时间复杂度：O(lgn)，非常高效。

特点
要求待查找的数组或者区间是排好序的。
对数组进行动态的删除和插入操作并完成查找，平均复杂度会变为 O(n)。

因此，当输入的数组或者区间是排好序的，同时又不会经常变动，而要求从里面找出一个满足条件的元素的时候，二分搜索就是最好的选择。


步骤：从已经排好序的数组或区间中取出中间位置的元素，判断该元素是否满足要搜索的条件，如果满足，停止搜索，程序结束。
如果正中间的元素不满足条件，则从它两边的区域进行搜索。由于数组是排好序的，可以利用排除法，确定接下来应该从这两个区间中的哪一个去搜索。
通过判断，如果发现真正要找的元素在左半区间的话，就继续在左半区间里进行二分搜索。反之，就在右半区间里进行二分搜索。 

  1. int binarySearch(int[] nums, int target) {
  2.     int left = 0, right = ...;
  4.     while(...) {
  5.         //计算 mid 时需要技巧防止溢出，建议写成: mid = left + (right - left) / 2
  6.         int mid = (right + left) / 2;
  7.         if (nums[mid] == target) {
  8.             ...
  9.         } else if (nums[mid] < target) {
  10.             left = ...
  11.         } else if (nums[mid] > target) {
  12.             right = ...
  13.         }
  14.     }
  15.     return ...;
  16. }
  18. 递归法：
  20. // 二分搜索函数的定义里，除了要指定数组 nums 和目标查找数 target 之外，
  21. 还要指定查找区间的起点和终点位置，分别用 low 和 high 去表示。
  22. int binarySearch(int[] nums, int target, int low, int high) {
  23.         // 为了避免无限循环，先判断，如果起点位置大于终点位置，表明这是一个非法的区间，
  24.         已经尝试了所有的搜索区间还是没能找到结果，返回 -1。 
  26.     if (low > high) {
  27.         return -1;
  28.     }
  29.     // 取正中间那个数的下标 middle。
  30.     int middle = low + (high - low) / 2;
  32.     // 判断一下正中间的那个数是不是要找的目标数 target，是，就返回下标 middle。    
  33.     if (nums[middle] == target) {
  34.         return middle;
  35.     }
  37.     // 如果发现目标数在左边，就递归地从左半边进行二分搜索。
  38.     if (target < nums[middle]) {
  39.         return binarySearch(nums, target, low, middle - 1);
  40.       } else {
  41.         return binarySearch(nums, target, middle + 1, high);
  42.     }//否则从右半边递归地进行二分搜索。
  43. }
  45. 注意：
  46. 在计算 middle 下标的时候，不能简单地用 (low + hight) / 2，可能会导致溢出。
  48. 在取左半边以及右半边的区间时，左半边是 [low, middle - 1]，右半边是 [middle + 1, high]，
  49. 这是两个闭区间。因为已经确定了 middle 那个点不是我们要找的，就没有必要再把它加入到左、右半边了。
  51. 对于一个长度为奇数的数组，如：{1, 2, 3, 4, 5}，按照 low + (high - low) / 2 来计算，middle 就是
  52. 正中间的那个位置，对于一个长度为偶数的数组，例如 {1, 2, 3, 4}，middle 就是正中间靠左边的一个位置。

分治

算法原理：

将一个数组元素大于 2 的数组分成两个子数组，然后对每一个子数组递归调用，直到最小的子数组的元素个数为 1 个或者是 2 个，此时就能直接得出最大值与最小值，然后逐步往上合并子数组，比较 2 个子数组的最大值与最小值，依次进行下去，最后就能找到整个数组的最大值与最小值。

解题步骤：

① 先解决小规模的问题，如数组中只有 1 个元素或者只有两个元素时候的情况；
② 将问题分解，如果数组的元素大于等于 3 个，将数组分为两个小的数组；
③ 递归的求解各子问题，将② 中分解的两个小的数组再进行以上两个步骤最后都化为小规模问题解决；
④ 合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。

例如：在n个元素中找出最大元素和最小元素。[-13，13，9，-5，7，23，0，15]
用直接比较法求出：

分治：
把n个元素分成两组；
分别求两组的最大值和最小值；
然后分别将这两组的最大值和最小值相比较，求出全部元素的最大值和最小值。
<如果A1和A2中的元素多于两个，则再用上述方法各分为两个子集。直至子集中元素至多两个元素为止。>

  1. import time
  3. def findbest(A, low, high):
  4.     if high - low <= 1:                 #如果数组中元素只剩下两个，则可以直接比较
  5.         if A[low] <= A[high]:
  6.             return A[high], A[low]
  7.         else:
  8.             return A[low], A[high]
  10.     mid = (low + high) // 2             #从中点分成两个子数组，进行递归查找
  11.     result1 = findbest(A, low, mid)
  12.     result2 = findbest(A, mid+1, high)
  13.     if result1[0] < result2[0]:         #比较找到的两个子数组的最大值的大小关系
  14.         if result1[1] < result2[1]:     #再比较找到的两个子数组的最小值的大小关系
  15.             return result2[0], result1[1]   #返回结果（最大值，最小值）
  16.         else:
  17.             return result2[0], result2[1]
  18.     else:
  19.         if result1[1] < result2[1]:
  20.             return result1[0], result1[1]
  21.         else:
  22.             return result1[0], result2[1]
  24. def main():
  25.     from random import sample
  26.     rand_array = sample([x for x in range(-1000, 1000)], 10)#在-1000~999中产生10个随机数
  27.     print(rand_array)
  28.     start = time.time()
  29.     result = findbest(rand_array, 0, 9)
  30.     print("最大值为：%d" %(result[0]))
  31.     print("最小值为：%d" %(result[1]))
  32.     end = time.time()
  33.     print("共耗时:\n" + str(end - start) + " s")
  36. if __name__ == '__main__':
  37.     main()

image.png

image.png

BFS：广度优先搜索

BFS 可以看成是层序遍历。从某个结点出发，BFS 首先遍历到距离为 1 的结点，然后是距离为 2、3、4…… 的结点。因此，BFS 可以用来求最短路径问题。BFS 先搜索到的结点，一定是距离最近的结点。

BFS 需要使用队列，代码框架是这样子的 在每层遍历前，记录队列中的结点数量 n，然后一口气处理完这一层的 n个结点
while queue 非空:
node = queue.pop()
for node 的所有相邻结点 m:
if m 未访问过:
queue.push(m)		 depth = 0 # 记录遍历到第几层
while queue 非空:
depth++
n = queue 中的元素个数
循环 n 次:
node = queue.pop()
for node 的所有相邻结点 m:
if m 未访问过:
queue.push(m)

leecode994腐烂橘子
题目要求：返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。翻译一下，求腐烂橘子到所有新鲜橘子的最短路径。
类似于岛屿问题，我们只需将所有的烂橘子的坐标存放到一个队列里面，然后通过BFS将附近的新鲜橘子腐蚀即可
输入：[[2,1,1],[1,1,0],[0,1,1]]
输出：4

  1. class Solution:
  2.     def Norange(self, grid):
  3.         n = len(grid)
  4.         m = len(grid[0])
  5.         queue = []   # 烂橘子队列，即BFS的0层节点的坐标
  7.         count = 0  # 新鲜橘子数量
  8.         for r in range(n):
  9.             for c in range(m):
  10.                 if grid[r][c] == 2:
  11.                     queue.append((r, c))
  12.                 elif grid[r][c] == 1:
  13.                     count += 1
  15.         round = 0   # 分钟数，轮数
  16.         while count > 0 and len(queue) > 0:
  17.             round += 1
  18.             for i in range(len(queue)):  # 遍历这一层的坏橘子
  19.                 r, c = queue.pop(0)  # 取出队列中第一个坏橘子的坐标
  21.                 if r + 1 < n and grid[r+1][c] == 1:   # 👇侧有好橘子
  22.                     grid[r+1][c] = 2
  23.                     count -= 1
  24.                     queue.append((r+1, c))
  25.                 if r - 1 >= 0 and grid[r-1][c] == 1:   # 👆侧有好橘子
  26.                     grid[r-1][c] = 2
  27.                     count -= 1
  28.                     queue.append((r-1, c))
  30.                 if c + 1 < m and grid[r][c+1] == 1:  # 👈侧有好橘子
  31.                     grid[r][c+1] = 2
  32.                     count -= 1
  33.                     queue.append((r, c+1))
  34.                 if c - 1 >= 0 and grid[r][c-1] == 1:   # 👉侧有好橘子
  35.                     grid[r][c-1] = 2
  36.                     count -= 1
  37.                     queue.append((r, c-1))
  39.         if count > 0:
  40.             return -1
  41.         else:
  42.             return round

DFS