- 顺序(线性)查找
- 二分查找/折半查找
- 插值查找
- 斐波那契查找
线性查找算法
- 思路分析
逐一对比 - Java
public class Chazhao {
public static void main(String[] args) {
int[] arr = {1, 9, 11, -1, 34, 89};
int index = lineSearch(arr, -11);
if(index == -1){
System.out.println("没有找到");
}else {
System.out.println("找到, 下标为: "+ index);
}
}
/**
* 线性查找
* @param arr 数组
* @param value 要查找的值
* @return 找到返回对应的下标，找不到返回-1
*/
public static int lineSearch(int[] arr, int value){
// 逐一对比
for(int i=0; i<arr.length; i++){
if(arr[i] == value){
return i;
}
}
return -1;
}
}
二分查找算法
- 思路分析
- 必须是有序数组
- 首先确定数组的中间的下标 mid = (left + right) /2
- 然后让要查找的值value和arr[mid]比较
- value > arr[mid], 说明要查找的值在mid右边, 继续递归向右查找
- value < arr[mid], 说明要查找的值在mid左边, 继续递归向左查找
- value = arr[mid], 找到
- Java
public class Chazhao {
public static void main(String[] args) {
int[] arr = {1, 23, 56, 110, 380, 1000, 3289};
int index = binarySearch(arr, 0, arr.length-1, 1000);
System.out.println(index); // 5
}
/**
* 二分查找法
* @param arr 数组
* @param left 左边索引
* @param right 右边索引
* @param value 查找的值
* @return 找到就返回下标, 找不到就返回-1
*/
public static int binarySearch(int[] arr, int left, int right, int value){
// 递归了整个数组， 没有找到
if(left > right){
return -1;
}
int mid = (left + right)/2;
int midVal = arr[mid];
if(value > midVal){ // 向右递归
return binarySearch(arr, mid+1, right, value);
}else if(value < mid){ // 向做递归
return binarySearch(arr, left, right+1, value);
}else {
return mid;
}
}
}
插值查找算法
- 原理
插值查找类似于二分查找, 不同的是插值查找每次从自适应mid处开始 - 自适应
插值查找和二分查找的区别就在这个自适应, 插值查找每次从自适应mid处开始
自适应mid有一个公式:
int mid = left + (right - left) * (value - arr[left]) / (arr[right] - arr[left])
arr是要查找的数组
left表示左边索引
right表示右边索引 - 注意事项
- 对于数据量较大, 关键值分布比较均匀时, 使用插值查找, 速度较快
- 关键值分布不均匀的情况下, 该方法不一定比折半查找好
- Java 代码实现
public class Chazhao {
// 记录递归了几次
static int count = 0;
public static void main(String[] args) {
// 初始化数据
int arr[] = new int[100];
for(int i=0; i<100; i++){
arr[i] = i+1;
}
// 查找数据
int index = insertValueSearch(arr, 0, arr.length-1, 78);
System.out.println("执行了"+count+"次递归");
System.out.println("要找的数字的下标为: "+index);
}
public static int insertValueSearch(int[] arr, int left, int right, int value){
count ++;
// 因为arr是有序数组, 可以直接通过arr[0] > value || arr[arr.length-1] < value可以判断是否数组的数值范围内
if(left > right || arr[0] > value || arr[arr.length-1] < value){
return -1;
}
// 求mid, 自适应
int mid = left + (right - left) * (value - arr[left]) / (arr[right] - arr[left]);
int midVal = arr[mid];
if(value > midVal){//大于中间值, 向右递归
return insertValueSearch(arr, mid+1, right, value);
}else if(value < midVal){//小于中间值, 向左递归
return insertValueSearch(arr, left, right-1, value);
}else {
return mid;
}
}
}
测试
执行了1次递归
要找的数字的下标为: 77
斐波那契(黄金分割法)查找算法
未完待续
