亲宝软件园·资讯

展开

算法思想 - 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. 查找第一个值等于给定值的元素位置
  2. 查找最后一个值等于给定值的元素位置
  3. 查找第一个大于等于给定值的元素位置
  4. 查找最后一个小于等于给定值的元素位置

这几个问题的代码都相对难写,代码实现如下:

 

 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 }

 

做个总结,分析一下二分查找的应用场景:
  1. 二分查找依赖于顺序表结构,如数组;在链表上直接运用二分查找效率低
  2. 二分查找需要数据是有序的,乱序的数据集合中无法应用,因为没有办法二分;所以对于相对静态的数据,排序后应用二分查找的效率还是很不错的;而对于动态变化的数据集合,维护成本会很高
  3. 数据量太小,发挥不出二分查找的威力;但是如果比较操作比较耗时,还是推荐使用二分查找
  4. 数据量太大,内存放不下
一个思考题:如何在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天内送达包裹的能力
有效括号的嵌套深度
元素和小于等于阈值的正方形的最大边长

 

加载全部内容

相关教程
猜你喜欢
用户评论