包括以下内容:
二分查找 key 在数组中的位置
二分查找数组中第一个大于或等于 key 的位置
二分查找数组中第一个大于 key 的位置
变量解释: int[] arr1; 记录查找表, 所有元素都是唯一的
int[] arr2; 记录查找表, 元素不唯一
测试用例:
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
arr1[] | 01 | 05 | 07 | 09 | 10 | 15 | 18 | 22 | 25 |
arr2[] | 01 | 01 | 07 | 07 | 15 | 15 | 15 | 22 | 25 |
一. 查找 key 在数组中的位置, 查找不成功则返回 - 1;
迭代实现:
- int binary_search1(int arr[], int low, int high, int key){
- while(low<=high){
- int mid = low + (high-low)/2;
- if(arr[mid]<key) low=mid+1;
- else if(arr[mid]>key) high=mid-1;
- else return mid;
- }
- return -1;
- }
递归实现:
- int binary_search(int arr[], int low, int high, int key){
- int mid = low+(high-low)/2;
- if(low>high) return -1;
- if(arr[mid]<key) return binary_search(arr, mid+1, high, key);
- if(arr[mid]>key) return binary_search(arr, low, mid-1, key);
- return mid;
- }
这里对递归实现, 做一定的解释:
首先这个函数的功能是在查找表 arr1[] 中查找 key 所在的位置, 如果查找成功则返回所在位置, 否则返回 - 1, 标志未查找成功; 二分查找的前提的查找表有序, 这里以查找表递增为例实现二叉查找;
每次调用函数, 是对整个数组查找, 需要查找表数组 arr, 查找范围的下限 low, 和上限 high, 以及要查找的值 key; 为了统一, 我们这里把上限 + 1, 后面做解释
二分查找的思路: 先拿 key 和查找表最中间的值比较:
1. 如果比中间值大, 则 key 只可能在查找表的右半边, 在查找表的右边进行二叉查找
2. 如果 key 比中间的值小, 那么 key 只可能在查找表的左半边, 在查找表的左边进行二叉查找
3. 如果相等, 则找到 key 所在 key 的位置
以查找 7 为例,
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
1 | 5 | 7 | 9 | 10 | 15 | 18 | 22 | 25 | ||
low | mid | high | 7 比 10 大,在查找表左边进行二叉查找, high=mid-1 | |||||||
low | mid | high | 7 比 5 大,在查找表的右边进行二叉查找, low=mid+1 | |||||||
low | mid | high | 找到 7,返回 7 所在位置 |
有几个需要注意的地方:
while 的循环条件: 应该是 low<=high, 而不是 low<high;
每次循环如果没有找到 key 所在的位置, 要修改 low=mid-1, 或者 high=mid+1; 不能是 low=mid, 或者是 high=mid, 否则会导致死循环
只适用于递增的查找表
二叉查找, 相当于在一颗平衡二叉树中进行查找, 平衡二叉树的高度 h=[logn]+1, n 是查找表的长度, 所以使用二叉树查找值得时候, 在 O(logn) 的时间内就能找到所需要查找的值, 及时查找失败, 比较次数也不会超过查找表对于的平衡二叉树的深度
二叉查找并不能保证比顺序查找的更优 , 对于查找概率相同的的 key 来说二叉树更优, 当查找表前面的值查找频率较高的时候, 顺序查找的效率可能比二叉查找更优
二. 查找表中第一个大于等于 key 的位置
- int lower_bound(int arr[], int low, int high, int key){
- while(low<high){
- int mid = low + (high-low)/2;
- if(key>arr[mid]) low=mid+1;
- else high=mid;
- }
- return low;
- }
函数解释: 在不减的查找表里面找第一个大于或者等于 key 的位置, 如果 key 在查找表中不存在, 返回的是 key 在数组中应该在的位置, 比如在 1,3,5 中查找 2, 返回的值是 1, 意思就是如果查找表中有 2 这个值, 他的位置应该在 1 这个位置, 如果 key 在查找表中, 返回的值就是 key 所在的位置; 解释一下上面的上限为什么要 + 1, 任然以 1,3,5 为例, 如果在表中查找 8, 传入 2 作为上限, 返回的值就是 2, 但这是错误的, 8 的位置应该在 3; 所以上限加一在于解决查找值 key 比查找表中所有元素还大的情况, 而对其他值得查找不会有影响;
这个函数和上面的函数很相似, 整体的框架类似, 但是存在一些细微的差别:
while 的循环判断条件不同
high 的修改条件不同
返回值不同
下面对这三点做出解释
在二分查找时, 有一个隐含条件是查找值 key 必须在查找表中, 当 low==high 以及确定了一个唯一的位置, 但是需要验证该位置的值是否等于 key; 但是在这个函数中, 我们要找的是第一个大于或等于 key 的位置, 如果 key 存在于查找表中, 那么当 low==hight 时, 查找表的值一定为 key, 不存在也没关系, 该位置即为 key 在查找表中应该所在的位置
因为我们要找的是第一个大于或者等于 key 所在位置, 那么当 arr[mid]<key 时, key 的位置肯定在 mid 的右边, 不可能在 mid 上, 因而 low=mid+1; 当 arr[mid]>key 时, key 的位置可能在 mid 的左边也可能就在 mid 上, 因为要找的是大于或等于 key 的值, 当 arr[mid]==key 的时候, key 的位置就在 mid 上, 让 high=mid, 经过几次迭代就能让 low==high, 从而退出循环, 可以发现后面两种情况是可以合并的, 将其合并在一起, 让代码精简一些
如果你手写实现一下该迭代过程, 就会发现终止循环的的情况一定是 low==high, 这种情况下确定了一个唯一的位置, 返回 low 和 high 其实都一样; 因为每一次迭代 low 的最大值即为 low=[(low+high)/2]+1, 改值一定是不大于 high 的当 low 等于 high 退出循环, 当 low 小于 high, 进行下一次迭代
以查找不存在的 8 为例, 正确的位置应该在 4;
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
1 | 1 | 7 | 7 | 15 | 15 | 15 | 23 | 25 | ||
low | mid | high | 8 小于 15,在 mid 左边进行查找, high=mid | |||||||
low | mid | high | 8 大于 7,在 mid 右边进行查找,low=mid+1 | |||||||
low, mid | high | 8 大于 7,在 mid 右边进行查找,low=mid+1 | ||||||||
low, high | low<high 条件不满足,返回 low 找到 key 应该在的位置 |
三. 查找第一个大于 key 所在的位置
- int upper_bound(int arr[], int low, int high, int key){
- while(low<high){
- int mid = low + (high-low)/2;
- if(key>=arr[mid]) low=mid+1;
- else high=mid;
- }
- return low;
- }
思路和查找第一个大于或等于 key 的位置的函数一样, 这里只需要把等于的条件放在左边即可; 这里不再做解释
lower_bound 和 upper_bound 组合使用能很方便的得到查找表中所有值等于 key 的左闭右开区间
通过相同的思路能能实现找到第一个小于或等于 key 的位置, 第一个等于 key 的位置;
来源: http://www.bubuko.com/infodetail-2671526.html