目录
1.顺序(线性)查找
1.1代码实现
package com.ws;
import java.util.ArrayList;
import java.util.List;
public class SeqSearch {
/**
* 顺序查找
* @param arr 要查的数组
* @param value 想查找的值
* @return 查找值的索引集合
*/
public static List<Integer> seqSearch(int[] arr, int value) {
List<Integer> resultList = new ArrayList<>();
for (int i = 0; i < arr.length; i++) {
if (arr[i] == value) {
resultList.add(i);
}
}
return resultList;
}
public static void main(String[] args) {
int[] arr = { 1, 5, 98, 5, 78, 35, 12, 100, 17, 15};
List<Integer> resultList = seqSearch(arr,5);
if(resultList.size() == 0) {
System.out.println("在数组中没有这个数~");
} else {
System.out.println(resultList);
}
}
}1.2查询结果
2.二分查找(折半查找)
二分查找的数组一定是有序的
2.1代码实现
package com.ws;
import java.util.ArrayList;
import java.util.List;
public class BinarySearch {
/**
* 二分查找
* @param arr 待查找数组
* @param value 想查找的目标值
* @param left 数组最左侧索引
* @param right 数组最右侧索引
* @return 目标值的索引集合
*/
public static List<Integer> binarySearch(int[] arr, int value, int left, int right) {
List<Integer> list = new ArrayList<>();
if (left > right) {
//退出递归时的条件
return list;
}
int mid = (left + right) / 2;
if (arr[mid] > value) {
//说明待查找值在左边 向左递归
return binarySearch(arr, value, left, mid-1);
} else if (arr[mid] < value) {
//说明待查找值在右边 向右递归
return binarySearch(arr, value, mid + 1, right);
} else { //arr[mid] == value 也就是找到的value
//先判断左面是否还有 = value的值 若有放在list集合中一起返回
int temp = mid -1;
while (true) {
if (temp < 0 || arr[temp] != value) { //退出
break;
}
list.add(temp);
temp--;
}
//左边遍历完成后 把mid 放在集合中 然后再遍历右边
list.add(mid);
//遍历右边 看是否有 = value的
temp = mid +1;
while (true) {
if (temp > right || arr[temp] != value) { //退出
break;
}
list.add(temp);
temp++;
}
return list;
}
}
public static void main(String[] args) {
int arr[] = { 1, 3, 5, 5, 7, 12, 34, 88};
List<Integer> list = binarySearch(arr,5,0,arr.length-1);
if(list.size() == 0) {
System.out.println("在数组中没有这个数~");
} else {
System.out.print(list);
}
}
}
结果:
3.插值查找算法
插值查找的数组一定是有序的
插值查找原理介绍:
插值查找算法类似于二分查找，不同的是插值查找每次从自适应 mid 处开始查找。
在二分查找中
mid = (left + right) / 2 = left + 1/2(right - left)
而插值查找中
mid = left + (right - left) *?(value - arr[left]) / (arr[right] - arr[left])
插值查找算法的举例说明
arr =[1,2,3,.......,100]假如我们需要查找的值1
使用二分查找的话，我们需要多次递归，才能找到1
使用插值查找算法
int mid = left + (right - left) *?(value - arr[left]) / (arr[right] - arr[left])
int mid = 0 + (99 - 0) * (1 - 1) / (100 - 1) = 0 + 99 * 0 / 99 =0
比如我们查找的值100
int mid = 0 + (99 - 0) * (100 - 1) / (100 - 1) = 0 + 99 * 99 / 99 =0 + 99= 99
3.1代码实现
package com.ws;
import java.util.ArrayList;
import java.util.List;
public class InsertValueSearch {
/**
* 插值查找 写法与二分查找如出一辙
* 唯一的区别就是 min的含义不同
* @param arr
* @param value
* @param left
* @param right
* @return
*/
public static List<Integer> insertValuSearch(int[] arr, int value, int left, int right) {
List<Integer> list = new ArrayList<>();
if (left > right || value < arr[left] || value > arr[arr.length - 1]) {
//退出递归时的条件
return list;
}
int mid = left + (right - left) * (value - arr[left]) / (arr[right] - arr[left]);
if (arr[mid] > value) {
//说明待查找值在左边 向左递归
return insertValuSearch(arr, value, left, mid-1);
} else if (arr[mid] < value) {
//说明待查找值在右边 向右递归
return insertValuSearch(arr, value, mid + 1, right);
} else { //arr[mid] == value 也就是找到的value
//先判断左面是否还有 = value的值 若有放在list集合中一起返回
int temp = mid -1;
while (true) {
if (temp < 0 || arr[temp] != value) { //退出
break;
}
list.add(temp);
temp--;
}
//左边遍历完成后 把mid 放在集合中 然后再遍历右边
list.add(mid);
//遍历右边 看是否有 = value的
temp = mid +1;
while (true) {
if (temp > right || arr[temp] != value) { //退出
break;
}
list.add(temp);
temp++;
}
return list;
}
}
public static void main(String[] args) {
//创建一个一到一百的有序数组
int[] arr = new int[100];
for (int i = 0; i < 100; i++) {
arr[i] = i + 1;
}
System.out.println(insertValuSearch(arr,1,0,99));
}
}
3.2结果:
4.斐波那契查找算法(黄金分割法)
斐波那契查找的数组一定是有序的
思想:就是把待查找数组的大小扩成满足斐波那契数列，然后用黄金分割点来找目标对象的值，其他的步骤与二分查找和插值查找相似；
mid = left + f[k -1] -1
4.1代码实现
import javax.xml.bind.annotation.XmlInlineBinaryData;
import java.util.Arrays;
public class FibonacciSearch {
static int MaxSize = 20;
/**
* 创建一个斐波那契队列
* @return
*/
public static int[] fib() {
int[] f = new int[MaxSize];
f[0] = 1;
f[1] = 1;
for (int i = 2; i < MaxSize; i++) {
f[i] = f[i - 1] + f[i - 2];
}
return f;
}
/**
* 斐波那契查找算法
* @param arr 待查找数组
* @param value 查找的目标值
* @return 目标值的下标
*/
public static int fibonacciSearch(int[] arr,int value) {
int left = 0;
int right = arr.length - 1;
//黄金分割点 mid = left + f[k -1] -1;
int mid = 0;
//k 是让数组刚好满足斐波那契数列的下标
int k = 0;
//创建一个斐波那契数列
int[] f = fib();
//使用while找到刚好满足数组大小的斐波那契数列k的值
//当然这个数组大小不可能恰好等于斐波那契数列 所以f[k]及有可能大于数组的长度
while (f[k] < arr.length) {
k++;
}
//创建一个数组 让他的大小刚好等于斐波那契数列的
//把arr给他 其余的暂时用0补齐
int[] temp = Arrays.copyOf(arr, f[k]);
//之前是暂时用0补齐 但是这会破坏数组的有序性 所以我们让它用arr的最后一位补齐
for (int i = right; i < temp.length; i++) {
temp[i] = arr[right];
}
//使用while循环找到目标值value
while (left <= right) {
mid = left + f[k -1] -1;
if (temp[mid] > value) {
//说明目标值在mid左边 向左找
right = mid -1;
//因为f[k] = f[k - 1] + f[k - 2]
//所以左边数组对应的斐波那契数列 就是k - 1;
k = k -1;
} else if (temp[mid] < value){
//说明目标值在mid右边 向右找
left = mid + 1;
//右边数组对应的斐波那契数列是k -2;
k = k - 2;
}else {
//因为 mid可能是临时是temp数组中 补齐的数据 那时我们直接返回right就好
if(mid <= right) {
return mid;
} else {
return right;
}
}
}
return -1;
}
public static void main(String[] args) {
int[] arr = new int[100];
for (int i = 0; i < 100; i++) {
arr[i] = i + 1;
}
int index = fibonacciSearch(arr,40);
System.out.println(index);
}
}
4.2结果
