顺序/线性查找算法

基本思想：逐一比较数列中的值，找到则返回。

很简单，这里给一个需求：

有一个数列：{1,8, 10, 89, 1000, 1234}，判断数列中是否包含此名称（顺序查找），要求：如果找到，则输出找到，并给出下标值

/**
  * 线性查找
  * @param arr 要查找数据的集合
  * @param value 要查找的数据
  * @return 对应元素的下标,没有找到返回-1
  */
public static int seqSearch(int[] arr,int value){
    for(int i = 0; i < arr.length; i++){
        if(arr[i] == value){
            return i;
        }
    }
    return -1;
}

int[] arr = {1,8, 10, 89, 1000, 1234};
int i = seqSearch(arr, 89);
if(i != -1){
    System.out.println("找到对应元素，下标为: " + i);
}else{
    System.out.println("没有找到元素");
}

二分查找/折半查找

请对一个 有序数组 进行二分查找 {1,8, 10, 89, 1000, 1234}，输入一个数看看该数组是否存在此数，并且求出下 标，如果没有就提示「没有这个数」。

二分查找可以使用 递归 和 非递归 实现，本次使用非递归方式实现。

思路分析

查找步骤：

1. 首先确定该数组的中间下标
2. 然后让需要查找的数（findVal）和 arr[mid] 比较
   1. findVal > arr[i]，说明要查找的数在 右 边
   2. findVal < arr[i] ，说明要查找的数在 左 边
   3. findVal == arr[i]，说明已经找到，就返回

什么时候结束递归？

1. 找到则结束递归

2. 未找到，则结束递归

   当 left > right 时，表示整个数组已经递归完。

代码实现

/**
  * 二分查找
  * @param arr 要查找数据的有序数组
  * @param left 开始查找左边索引
  * @param right 开始查找右边索引
  * @param findVal 要查找的值
  * @return 如果找到返回对应位置的索引，没有找到返回-1
  */
public static int binarySearch(int[] arr,int left,int right,int findVal){
    if(left > right){//遍历完没有找到数据
        return -1;
    }
    int mid = (left + right) / 2;
    int midVal = arr[mid];
    if(findVal > midVal){
        //在右边
        return binarySearch(arr,mid+1,right,findVal);
    }else if(findVal < midVal){
        //在左边
        return binarySearch(arr,left,mid-1,findVal);
    }else{//找到了
        return mid;
    }
}

上面二分查找只能查找一个值，如果要查找的值有多个值，则不能将其全部返回，对上面代码进行改进:

public static List<Integer> binarySearch2(int[] arr, int left, int right, int findVal){
    if(left > right){//遍历完没有找到数据
        return new ArrayList<>();
    }
    int mid = (left + right) / 2;
    int midVal = arr[mid];
    if(findVal > midVal){
        //在右边
        return binarySearch2(arr,mid+1,right,findVal);
    }else if(findVal < midVal){
        //在左边
        return binarySearch2(arr,left,mid-1,findVal);
    }else{//找到了
        ArrayList<Integer> list = new ArrayList<Integer>();
        list.add(mid);
        int temp = mid -1 ;
        while(true){//向左边扫描
            if(temp < 0 || findVal != arr[temp]){
                break;
            }
            list.add(temp);
            temp -= 1;
        }

        temp = mid + 1;
        while(true){//向右边扫描
            if(temp > arr.length-1 || findVal != arr[temp]){
                break;
            }
            list.add(temp);
            temp += 1;
        }

        return list;
    }
}

插值查找

查找原理

1. 查找查找算法 类似二分查找

   不同的是插值查找每次从 自适应 mid 处开始查找

2. 将折半查找中求 mid 的索引公式进行改进

• low：表示左边索引
• high：表示右边所以
• key：表示要查找的值

将折半查找中的 二分之一 这个系数进行改写，其他不变。

3. 改写后的查找索引求值为int mid = low + (high - low) * (key -arr[low]) / (arr[high] - arr[low])

代码实现

/**
     * 插值查找 二分查找的优化
     * @param arr 要查找数据的有序数组
     * @param left 左边索引
     * @param right 右边索引
     * @param findVal 要查找的值
     * @return
     */
public static int insertSearch(int[] arr,int left,int right,int  findVal){
    System.out.println("hel");
    //findVal < arr[left] || findVal > arr[right]不能省略，否则mid可能出现栈溢出
    if(left > right || findVal < arr[left] || findVal > arr[right]){
        return -1;
    }

    int mid = left + (right - left)*(findVal - arr[left])/(arr[right] - arr[left]);
    int midVal = arr[mid];
    if(midVal < findVal){
        return insertSearch(arr,mid+1,right,findVal);
    }else if(midVal > findVal){
        return insertSearch(arr,left,mid-1,findVal);
    }else{
        return mid;
    }
}

注意事项

1. 对于 数据量较大，关键字分布比较均匀 的查找表来说，采用 插值查找，速度较快
2. 关键字分布 不均匀 的情况下，该方法不一定比折半查找要好