算法思想 - 01 二分思想
shniu 人气:1从一个例子开始，两个人进行猜数游戏，其中一个人写下一个数字，另外一个人猜，每猜一个数，给这个人说大了还是小了，继续猜，比如猜一个100以内的数，写下的数是64，最多猜7次就可以猜到这个数，这里就使用了二分思想。
二分思想是一个应用很广泛的思想，比如对于一个有序数组，它能将查找效率从O(n)优化到O(logn)，因为每次可以将范围缩小为上一次的一半。这是在数组中的应用场景，我们以这个为基础来分析一下二分查找的时间复杂度
对于一个有 n 个元素的有序数组中，每次查找后缩小数据范围为上一次的二分之一，所以有 n/2 , n/4 , n/8, … , n/(2^k)
当 n/(2^k) = 1 时，得到最终结果，则 k = logn，记作二分查找的时间复杂度 O(logn)，是一个非常高效的算法；举个例子，如果我们在一个40亿的数据中查找某个数，也只需要32次，相对于顺序查找效率提升了太多，可见其威力。
总结一下，二分查找是针对一个有序集合，每次通过将要查找的数据范围缩小为上一次的一半，直到找到目标值，或者区间缩小为0。二分查找正是在有序数组上应用了二分思想。
二分思想其实是一种解决问题的思想，为了加速查找效率而生，所谓的二分并不代表一定是二，也可以是三，可以是N，只是一种表述，表达的意思是以最快的速率将搜索数据的范围缩小。
二分思想在有序数组上的应用及其变形
二分细想在数组上的实现算法是二分查找，二分查找的一般实现，有几个需要注意的点
1 public class BinarySearch {
2 // 二分查找实现
3 public static int search(int[] arr, int target) {
4 int low = 0, high = arr.length - 1;
5
6 // 这里的中止条件是 low <= high, 因为 high = arr.length - 1
7 while (low <= high) {
8 // 使用 low + (high - low) / 2, 而不使用 (high + low) / 2, 是因为 high + low 可能造成整型溢出
9 // int mid = low + (high - low) / 2; // 这种方式是可以的，不如位运算效率高
10 int mid = low + ((high - low) >> 1); // 这种方式是最优的，效率最高
11
12 if (arr[mid] == target) {
13 return mid;
14 } else if (arr[mid] > target) {
15 high = mid - 1;
16 } else {
17 low = mid + 1;
18 }
19 }
20 return -1;
21 }
22
23 // 利用递归实现二分查找
24 public static int searchRecursive(int[] arr, int target) {
25 return recurSearch(arr, target, 0, arr.length - 1);
26 }
27 private static int recurSearch(int[] arr, int target, int left, int right) {
28 // terminator
29 if (left > right)
30 return -1;
31
32 int mid = left + ((right - left) >> 1);
33
34 if (arr[mid] == target) {
35 return mid;
36 } else if (arr[mid] > target) {
37 return recurSearch(arr, target, left, mid - 1);
38 } else {
39 return recurSearch(arr, target, mid + 1, right);
40 }
41 }
42 }
以上是一个常规的二分查找实现，这个数组中没有重复元素，查找给定值的元素，但是还有更难的：
- 查找第一个值等于给定值的元素位置
- 查找最后一个值等于给定值的元素位置
- 查找第一个大于等于给定值的元素位置
- 查找最后一个小于等于给定值的元素位置
这几个问题的代码都相对难写，代码实现如下：
1 class BinarySearchExt {
2 // 查找第一个值等于给定值的元素位置
3 public static int searchFirst(int[] arr, int target) {
4 int left = 0, high = arr.length - 1;
5
6 while (left <= right) {
7 int mid = left + (right - left) / 2;
8 if (arr[mid] > target) {
9 right = mid - 1;
10 } else if (arr[mid] < target) {
11 left = mid + 1;
12 } else {
13 if (mid == 0 || arr[mid - 1] != target) return mid;
14 else high = mid - 1;
15 }
16 }
17
18 return -1;
19 }
20
21 // 查找最后一个值等于给定值的元素位置
22 public static int searchLast(int[] arr, int target) {
23 int left = 0, high = arr.length - 1;
24 while (left <= right) {
25 int mid = left + (right - left) / 2;
26 if (arr[mid] > target) {
27 right = mid - 1;
28 } else if (arr[mid] < target) {
29 left = mid + 1;
30 } else {
31 if ((mid == arr.length - 1) || (arr[mid + 1] != target)) return mid;
32 else left = mid + 1;
33 }
34 }
35 return -1;
36 }
37
38 // 查找第一个大于等于给定值的元素位置
39 public static int searchGte(int[] arr, int target) {
40 int left = 0, right = arr.length - 1;
41 while (left <= right) {
42 int mid = left + ((right - left) >> 1);
43 if (arr[mid] >= target) {
44 if ((mid == 0) || (arr[mid - 1] < target)) return mid;
45 else right = mid - 1;
46 } else {
47 left = mid + 1;
48 }
49 }
50 return -1;
51 }
52
53 // 查找最后一个小于等于给定值的元素位置
54 public static int searchLte(int[] arr, int target) {
55 int left = 0, right = arr.length - 1;
56 while (left <= right) {
57 int mid = left + ((right - left) >> 1);
58 if (arr[mid] <= target) {
59 if ((mid == arr.length - 1) || (arr[mid + 1] > target)) return mid;
60 else left = mid + 1;
61 } else {
62 right = mid - 1;
63 }
64 }
65 return -1;
66 }
67 }
做个总结，分析一下二分查找的应用场景：
- 二分查找依赖于顺序表结构，如数组；在链表上直接运用二分查找效率低
- 二分查找需要数据是有序的，乱序的数据集合中无法应用，因为没有办法二分；所以对于相对静态的数据，排序后应用二分查找的效率还是很不错的；而对于动态变化的数据集合，维护成本会很高
- 数据量太小，发挥不出二分查找的威力；但是如果比较操作比较耗时，还是推荐使用二分查找
- 数据量太大，内存放不下
一个思考题：如何在1000万整数中快速查找某个整数呢？要求内存限制是100M，可以使用二分查找，先对1000万整数分配一个数组，然后进行排序，然后再使用二分查找。其他的方法，可能无法满足内存限制的问题，比如散列表、跳表、AVL树等。
另外一个思考题：如何快速定位一个IP的归属地？假设有10万+的IP地址段和归属地的映射关系，我们先对IP地址段的起始地址转成整数后排序，利用二分查找“在有序数组中，查找最后一个小于等于给定值的元素位置“，这样就可以找到一个ip段，然后取出来判断是不是在这个段里，不在的话，返回未找到；否则返回对应的归属地。
延伸之链表上的二分思想应用
上面，我们分析说在链表上应用二分查找的效率很低，那么为什么呢？分析一下
假设有n个元素的有序链表，现在用二分查找搜索数据，第一次移动指针次数 n/2，第二次移动 n/4，一直到 1，所以总的移动次数相加就是 n-1 次 可见时间复杂度是 O(n), 这个和顺序查找链表的时间复杂度 O(n) 是同级别的，其实二分查找比顺序查找的效率更低，因为它做了更多次无谓的指针移动
我们知道了二分思想直接应用到链表上是不可行的，有没有其他的办法，其实有，就是为有序链表增加多级索引，在搜索的时候根据索引应用二分思想。
二分查找常见的算法题目
搜索插入位置，这是一道二分查找的直接应用
实现如下
1 class Solution {
2 public int searchInsert(int[] nums, int target) {
3 int left = 0, right = nums.length - 1;
4
5 int pos = -1;
6 while (left <= right) {
7 int mid = left + (right - left) / 2;
8 if (nums[mid] == target) {
9 pos = mid;
10 break;
11 } else if (nums[mid] > target) {
12 right = mid - 1;
13 } else {
14 left = mid + 1;
15 }
16 }
17 return pos == -1 ? left : pos;
18 }
19 }
搜索二维矩阵
搜索二维矩阵II
有序矩阵中第K小的元素
两数相除
搜索旋转排序数组
这个题目也是二分查找的一个拓展题目，代码实现如下
1 class Solution {
2 public int search(int[] nums, int target) {
3 if (nums.length == 1) return nums[0] == target ? 0 : -1;
4 int low = 0, high = nums.length - 1;
5
6 while (low <= high) {
7 int mid = low + (high - low) / 2;
8
9 if (nums[mid] == target) return mid;
10
11 // 这里是关键
12 // nums[low] <= target && target < nums[mid] 表示 low mid 是有序的，且target在它们中间，需要将high向前移动
13 // nums[low] > nums[mid] && target > nums[high] 表示 low ~ mid 是无序的，而且 target 比 high 位置的元素还要大，因为 mid ~ high 是有序的，所以必然在 low ~ mid 中间，移动high
14 // nums[low] > nums[mid] && target < nums[mid] 表示 low ~ mid 是无序的, 而且 target 比mid位置处的值还要小，因为 mid ~ high 是有序的，所以必然在 low ~ mid 中间，移动high
15 // 否则，就是移动low
16 if ((nums[low] <= target && target < nums[mid]) ||
17 (nums[low] > nums[mid] && target > nums[high]) ||
18 (nums[low] > nums[mid] && target < nums[mid])) {
19 // 这里是
20 high = mid - 1;
21 } else {
22 low = mid + 1;
23 }
24 }
25
26 return low == high && nums[low] == target ? low : -1;
27 }
28 }
搜索旋转排序数组II
在排序数组中查找元素的第一个位置和最后一个位置
Pow(x,n)
x的平方根，如果是精确到小数后6位呢？
有效的完全平方数
寻找旋转排序数组中的最小值
1 class Solution {
2 // 关键是边界
3 public int findMin(int[] nums) {
4 int low = 0, high = nums.length - 1;
5 int lastElement = nums[high];
6 while (low < high) {
7 int mid = low + ((high - low) >> 1);
8 // 比最后一个元素小，说明转折点必定在mid的左边, 搜索左边
9 if (nums[mid] < lastElement) high = mid;
10 // 否则在右边
11 else low = mid + 1;
12 }
13 return nums[low];
14 }
15 }
寻找峰值
长度最小的子数组
完全二叉树的节点个数
二叉搜索树第K小的元素
寻找重复数
最长上升子序列
两个数组的交集
两个数组的交集II
寻找右区间
找到K个最接近的元素
基于时间的键值存储
在D天内送达包裹的能力
有效括号的嵌套深度
元素和小于等于阈值的正方形的最大边长
加载全部内容