查找算法

常用的查找算法有:

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

1、二分查找算法

1.1 二分查找思路分析

二分查找的条件:

  • 查找的数量只能是一个,从指定一组数据中查找一个需要的数据
  • 二分查找用于查找的数据,逻辑上应该是有序的

因为数组时有序的,首先找到要查找的数组中间位置的下标

然后将要查找的数和 arr[mid] 数组中间位置的值进行比较

如果要找的数与中间数相等,就返回

如果要查找的数在中间数的左边,向左递归进行查找,在右边就向右递归进行查找

如果递归完整个数组仍未找到要找的数,结束递归退出

1.2 二分查找代码实现

给定一个数组内元素有序的数组,通过二分查找找到需要查找的数的位置,如果值存在返回下标,否则返回 -1

下面数组中所有元素是不重复的

public static void main(String[] args) {
   
     
    int[] arr = {
   
     1,3, 5, 32, 34, 234};
    int i = binarySearch(arr, 0, arr.length - 1, 34);
    System.out.println(i);
}

/**
     * 二分查找算法
     * @param arr   数组
     * @param left  左边的索引
     * @param right 右边的索引
     * @param finalVal  要查找的值
     * @return  找到返回下标,未找到返回 -1
     */
public static int binarySearch(int[] arr, int left, int right, int finalVal) {
   
     
    int mid = (left + right) / 2; // 找到中间位置 mid
    int midValue = arr[mid]; // 中间位置的值 midValue
    // 左边下标大于右边,返回 -1
    if (left > right) {
   
     
        return -1;
    }
    // 看要查找的值在中间位置值的左边还是右边,进行递归。如果中间值为要查找的值则返回
    if (finalVal > midValue) {
   
     
        return binarySearch(arr, mid + 1, right, finalVal);

    } else if (finalVal < midValue) {
   
     
        return binarySearch(arr, left, mid - 1, finalVal);
    } else {
   
     
        return mid;
    }
}