常用查找算法

顺序查找

• 适合于存储结构为顺序存储或链接存储的线性表。顺序查找也称为线形查找，属于无序查找算法

  public static int orderLookUp(int[] nums,int num){
      for (int i = 0; i < nums.length; i++) {
          if (num==nums[i]) {
              return i;
          }
      }
      return -1;
  }
  

• 复杂度：O(n)

二分查找

• 前提：有序，物理连续（能够随机访问）

  public static int halfLookUp(int[] nums, int num) {
      int start = 0;
      int end = nums.length - 1;
      SortAlgorithm.quickSwap(nums, 0, end);
      for (int i = 0; i < nums.length; i++) {
          if (num == nums[i]) {
              return i;
          }
      }
      int mid;
      while (start <= end) {
          mid = (start + end) / 2;
          if (nums[mid] < num) {
              start = mid + 1;
          } else if (nums[mid] > num) {
              end = mid - 1;
          } else {
              return mid;
          }
      }
      return -1;
  }
  

• 数据已经有序排放在数组中，通过将待查的元素与数组最中间元素进行对比，如果大于中间值，则目标值可能存在于右半部分，否则可能在左半部分，查到为止

二分查找扩展

• 插值

  基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，差值查找也属于有序查找。

  注意：对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择。

  复杂度：O(log2(log2n))

• 斐波那契

  也是二分查找的一种提升算法，通过运用黄金比例的概念在数列中选择查找点进行查找，提高查找效率。同样地，斐波那契查找也属于一种有序查找算法

树型查找

• 二叉查找树是先对待查找的数据进行生成树，确保树的左分支的值小于右分支的值
• 破坏原有结构