现在比较常用几种查找算法分别为顺序查找，二分查找，插值查找，裴波那契查找这四种算法。
顺序查找不用多说，大家都在用。

二分查找

二分查找又称折半查找，它是一种效率较高的查找方法。
要求：要查找的顺序必须是有序的。

基本思想：
image.png
将要查找的数据拆分成一半一半。
mid为中间值，比mid小的去左边查，比mid大的去右边查。
然后循环往复直到遍历结束或者找到要查询的值

  1.     /**
  2.      * 二分查找
  3.      * @param arr   要查询的数组
  4.      * @param left  左边的索引
  5.      * @param right 右边的索引
  6.      * @param val   要查询的值
  7.      * @return      返回index，-1 为未找到
  8.      */
  9.     public static int binarySearch(int[] arr, int left, int right, int val) {
  10.         //递归出口，遍历完成但是没有找到值。
  11.         if (left > right) {
  12.             return -1;
  13.         }
  15.         int mid = (left + right) / 2;
  16.         int midVal = arr[mid];
  18.         if (val > midVal) {
  19.             return binarySearch(arr, mid + 1, right, val);
  20.         }else if (val < midVal) {
  21.             return binarySearch(arr, left, mid - 1, val);
  22.         }else {
  23.             return mid;
  24.         }
  26.     }

插值查找

插值查找和二分类似，就是mid的公式发生了改变。
image.png
其实这几个所谓的查找算法，好像也就mid的公式不一样。

  1.     //插值查找
  2.     public static int interPolationSearch(int[] arr, int left, int right, int findValue) {
  3.         //防止越界
  4.         if(left > right || findValue < arr[left] || findValue > arr[right]) {
  5.             return -1;
  6.         }
  8.         //由于取整的关系， a*b/c 不等于 a/c*b
  9.         int mid = left + (right - left) * (findValue - arr[left]) / (arr[right] - arr[left]);
  10.         int midVal = arr[mid];
  11.         if(findValue > midVal) {
  12.             return interPolationSearch(arr, mid + 1, right, findValue);
  13.         }else if(findValue < midVal) {
  14.             return interPolationSearch(arr, left, mid - 1, findValue);
  15.         }else {
  16.             return mid;
  17.         }

裴波那契查找作为扩展