Java数据结构与算法：查找算法

在java中，我们常用的查找有四种:

1. 顺序(线性)查找
1. 二分查找/折半查找
1. 插值查找
1. 斐波那契查找

1、线性查找

线性查找是最简单也是最基本的查找了，其思想就是遍历数组中所有的值来与查找值相比较，找到了就返回。

2、二分查找

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
基本思路：首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
时间复杂度：对数时间O(㏒₂n)
注意！！二分查找的数组中数据必须是顺序结构，也就是已经排好序的。

递归代码实现：

public static void main(String[] args) {
      int[] arr = {1,2,3,4,5,6,7,8,9,10};
     
     System.out.println(find(arr,0,0,arr.length - 1));
  }
  
  public static int find(int[] arr,int value,int left,int right) {
      int mid = (left + right) / 2;
      
      if(value > arr[mid] && mid < right) {
          return find(arr,value,mid + 1,right);
      }else if(value < arr[mid] && mid > left) {
          return find(arr,value,left,mid - 1);
      }else if(value == arr[mid]) {
          return mid;
      }else {
          return -1;
      }           
  }

非递归代码实现：

 public static void main(String[] args) {
     int[] arr = {1,2,3,4,5,6,7,8,90,1000000};
     binaryFind(arr,1000000);
}

public static void binaryFind(int[] arr,int val) {
    int mid = (arr.length-1)/2;
    int left = 0;
    int right = arr.length - 1;
    while(left <= right) {
        if(arr[mid] > val) {
            right = mid - 1;
            mid = (left + right)/2;
        }else if(arr[mid] == val) {
            System.out.println(mid + "和" + arr[mid]);
            break;
        }else if(arr[mid] < val) {
            left = mid + 1;
            mid = (left + right)/2;
        }
    }
}

3.插值查找

插值查找算法类似于二分查找，不同的是插值查找每次从自适应mid处开始查找。
将折半查找中的求mid 索引的公式 , low 表示左边索引left, high表示右边索引right.key 就是前面二分里面的value
注意事项：对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找, 速度较快.
关键字分布不均匀的情况下，该方法不一定比折半查找要好

代码实现（和二分法基本一模一样，只是改了mid的赋值）：

     public static void main(String[] args) {
      int[] arr = {1,2,3,4,5,6,7,8,9,10000000};
     
     System.out.println(find(arr,9,0,arr.length - 1));
  }
  
  public static int find(int[] arr,int value,int left,int right) {
      int mid = left + ((value - arr[left])/(arr[right] - arr[left])) * (right - left);
      
      if(value > arr[mid] && mid < right) {
          return find(arr,value,mid + 1,right);
      }else if(value < arr[mid] && mid > left) {
          return find(arr,value,left,mid - 1);
      }else if(value == arr[mid]) {
          return mid;
      }else {
          return -1;
      }           
  }

4.斐波那契(黄金分割法)查找算法

斐波那契查找原理与前两种相似，仅仅改变了中间结点（mid）的位置，mid不再是中间或插值得到，而是位于黄金分点附近，即mid=low+F(k-1)-1（F代表斐波那契数列），如下图所示：

对F(k-1)-1的理解：
由斐波那契数列 F[k]=F[k-1]+F[k-2] 的性质，可以得到（F[k]-1）=（F[k-1]-1）+（F[k-2]-1）+1 。该式说明：只要顺序表的长度为F[k]-1，则可以将该表分成长度为F[k-1]-1和F[k-2]-1的两段，即如上图所示。从而中间位置为mid=low+F(k-1)-1
类似的，每一子段也可以用相同的方式分割但顺序表长度n不一定刚好等于F[k]-1，所以需要将原来的顺序表长度n增加至F[k]-1。这里的k值只要能使得F[k]-1恰好大于或等于n即可，由以下代码得到,顺序表长度增加后，新增的位置（从n+1到F[k]-1位置），都赋为n位置的值即可。

代码实现：

static int maxSize = 20;  
  public static void main(String[] args) {
      int[] arr = {1,2,3,4,5,6,7,8,9,10,11,12,13,14};
     
     System.out.println(find(arr,14));
  }
  
 //生成斐波那数列
  public static int[] fib() {
      int[] f = new int[maxSize];
      f[0] = 1;
      f[1] = 1;
      for(int i = 2;i < f.length;i++) {
          f[i] = f[i - 1] + f[i - 2];
      }
      return f;
  }
  
  public static int find(int[] arr,int value) {
      int l = 0;
      int r = arr.length - 1;
      int k = 0; //斐波那数列的下标
      int mid = 0;
      int[] f = fib();
      while(r > f[k] - 1) {
          k++;
      }
      int[] temp = Arrays.copyOf(arr, f[k]);
      for(int i = r + 1;i < temp.length;i++) {
          temp[i] = arr[r];
      }
      while(l <= r) {
          mid = l + f[k-1] - 1;
          if(value < temp[mid]) {
              r = mid - 1;
              k--;
          }else if(value > temp[mid]) {
              l = mid + 1;
              k -= 2;
          }else {
              if(mid <= r) {
                  return mid;
              }else {
                  return r;
              }
          }
              }
      return -1;
  }