一, 折半查找
1, 折半查找也没啥好说的, 就跟大家翻微信通讯录一样, 你想找个姓杨的, 你随手往下一划, 划到了个姓李的, 那这时候你肯定要从李往下划, 李之上的区域直接被你排除了.
所以我们要两个引用, 一个指向首, 一个指向尾, 再要另外一个指针指向中间, 你拿目标 value 跟 midValue 比较一下, 就知道目标再 mid 之前还是之后了. 假如说在 mid 之前, 这时候你让指向尾部的引用, 改为指向 mid-1 的位置, mid 指向此时的首尾之间, 继续比较, 直到找到目标.
2, 代码实现
- package Search.OrderedList;
- import java.util.Comparator;
- import java.util.List;
- public class Binary_Search {
- public static int Binary_Search(List<Integer> list, int key){
- list.sort(new Comparator<Integer>() {
- @Override
- public int compare(Integer integer, Integer t1) {
- return integer - t1;
- }
- });
- int low = 0;
- int high = list.size();
- while (low <= high){
- int mid = getMid(low, high);
- if (key> list.get(mid)){
- low = mid + 1;
- }else if (key <list.get(mid)){
- high = mid - 1;
- }else {
- return mid;
- }
- }
- return -1;
- }
- private static int getMid(int low, int high) {
- return (low + high) / 2;
- }
- }
3, 折半查找还是比较好理解的, 我们可以把查找过程想象成一棵完全二叉树, 最大的查找次数就是树的深度. 完全二叉树的最大结点数 n = 2k-1,k 是深度, 所以 k = log2(n+1), 即折半查找时间复杂度是 O(log(n)), 它远远好过顺序查找的 O(n). 但前提是数据来源为有序表. 但对于需要频繁插入删除操作的数据集来说, 维护有序的排序也需要不小的工作量.
二, 插值查找
插值查找是把折半查找中 mid 的计算方法从一半改为了
(a[] 是目标数组)
插值查找的时间复杂度不变, 但对于关键字分布比较均匀的查找表来说, 插值查找的平均性能要比折半查找好得多; 繁殖, 如果数组是极端不均匀的数据, 那么插值查找未必是好的选择.
三, 斐波那契查找
斐波那契查找也是对于折半查找的改进, 我们在前面栈的文章中有介绍过斐波那契数列求兔子繁殖的问题. 下面我们来看它在查找中的使用
斐波那契查找是利用黄金分割原理来实现的.
首先我们理解斐波那契数列的规律, 前两个数字的和等于后一个数字, 而恰好, 前两个数字满足黄金分割的关系. 我们利用这个关系来构造用来比较的数组. 首先我们拿到表的长度 n, 到斐波那契数列中去查找 n, 找到 n 属于 F[k-1]和 F[k]之间, 我们取 F[k], 此时 F[k]>= n
然后我们把数列长度补全为 F[k]-1, 不足的部分用表尾最后一个元素补齐. 然后我们把表分为两部分, 首先我们让 mid 指向 low + F[k] - 1, 也就是黄金分割点, 此时 mid 之前和之后刚好满足, mid - low = F[k - 1] -1 ; high - mid = F[k - 2] - 1. 于是我们就得到了新的分割方法.
代码实现:
- package Search.OrderedList;
- import java.util.List;
- public class Fibonacci_Search {
- private static int[] F = new int[100];
- public static int Fibonacci_Search(List<Integer> list, int key) throws Exception {
- int low = 0;
- int high = list.size() - 1;
- int n = list.size() - 1;
- int k = 0;
- int mid;
- while (n> F[k] - 1){
- k++;
- }
- for (int i = n; i <F[k] - 1; i++)
- {
- list.set(i, list.get(list.size() - 1));
- }
- while (low <= high){
- mid = low + F[k - 1] - 1;
- if (key < list.get(mid)){
- high = mid - 1;
- k = k - 1;
- } else if (key> list.get(mid)) {
- low = mid + 1;
- k = k - 2;
- }else {
- if (mid <= n){
- return mid;
- }else {
- return n;
- }
- }
- }
- return -1;
- }
- }
总结:
平均性能平均性能: 斐波那契>折半>插值
因为折半查找进行加法与除法运算(mid = (low + high) / 2), 插值查找进行复杂的四则运算( mid = low + (key - a[low] / (a[high] - a[low]) * (high - low)) ), 而斐波那契查找只是运用简单加减法运算 (mid = low + f[k-1] -1) , 在海量的数据查找过程中, 这种席位的差别会影响最终的查找效率. 三种有序表的查找本质上是分割点的选择不同, 各有优劣, 实际开发可根据数据的特点综合考虑再做决定.
[从今天开始修炼数据结构]有序表查找
来源: http://www.bubuko.com/infodetail-3360212.html