目录
基本查找-重要
二分查找-重要
插值查找-重要
斐波那契查找
分块查找-重要
哈希查找
树表查找
基本查找-重要
也叫做顺序查找（顺序查找适合于存储结构为数组或者链表）
基本思想：顺序查找也称为线形查找，属于无序查找算法。从数据结构线的一端开始，顺序扫描，依次将遍历到的结点与要查找的值相比较，若相等则表示查找成功；若遍历结束仍没有找到相同的，表示查找失败。
public class A01_BasicSearchDemo1 {
public static void main(String[] args) {
//基本查找/顺序查找
//核心：
//从0索引开始挨个往后查找
//需求：定义一个方法利用基本查找，查询某个元素是否存在
//数据如下：{131, 127, 147, 81, 103, 23, 7, 79}
int[] arr = {131, 127, 147, 81, 103, 23, 7, 79};
int number = 82;
System.out.println(basicSearch(arr, number));
}
//参数：
//一：数组
//二：要查找的元素
//返回值：
//元素是否存在
public static boolean basicSearch(int[] arr, int number){
//利用基本查找来查找number在数组中是否存在
for (int i = 0; i < arr.length; i++) {
if(arr[i] == number){
return true;
}
}
return false;
}
} // 定义一个方法利用基本查找，查询某个元素在数组中的索引
// 不考虑数组中元素是否重复
public static int findIndex(int[] array, int target) {
for (int i = 0; i < array.length; i++) {
if (array[i] == target) {
return i; // 找到目标元素，返回索引
}
}
return -1; // 没有找到目标元素，返回-1
} // 定义一个方法利用基本查找，查询某个元素在数组中的索引
// 考虑数组中元素有重复的可能性
public static List<Integer> findIndexes(int[] array, int target) {
List<Integer> list = new ArrayList<>();
for (int i = 0; i < array.length; i++) {
if (array[i] == target) {
list.add(i); // 找到目标元素，将索引添加到列表中
}
}
return list;
}二分查找-重要
也叫做折半查找，提高查找效率（元素必须是有序的，从小到大，或者从大到小都可以）
如果是无序的，也可以先进行排序。但是排序之后，会改变原有数据的顺序，查找出来元素位置跟原来的元素可能是不一样的，所以排序之后再查找只能判断当前数据是否在容器当中，返回的索引无实际的意义。
基本思想：也称为是折半查找，属于有序查找算法。用给定值先与中间结点比较。比较完之后有三种情况：
相等
说明找到了
要查找的数据比中间节点小
说明要查找的数字在中间节点左边
要查找的数据比中间节点大
说明要查找的数字在中间节点右边
public class A02_BinarySearchDemo1 {
public static void main(String[] args) {
//二分查找/折半查找
//核心：
//每次排除一半的查找范围
//需求：定义一个方法利用二分查找，查询某个元素在数组中的索引
//数据如下：{7, 23, 79, 81, 103, 127, 131, 147}
int[] arr = {7, 23, 79, 81, 103, 127, 131, 147};
System.out.println(binarySearch(arr, 150));
}
public static int binarySearch(int[] arr, int number){
//1.定义两个变量记录要查找的范围
int min = 0;
int max = arr.length - 1;
//2.利用循环不断的去找要查找的数据
while(true){
if(min > max){
return -1;
}
//3.找到min和max的中间位置
int mid = (min + max) / 2;
//4.拿着mid指向的元素跟要查找的元素进行比较
if(arr[mid] > number){
//4.1 number在mid的左边
//min不变，max = mid - 1；
max = mid - 1;
}else if(arr[mid] < number){
//4.2 number在mid的右边
//max不变，min = mid + 1;
min = mid + 1;
}else{
//4.3 number跟mid指向的元素一样
//找到了
return mid;
}
}
}
}改进： （插值算法）
mid=min+(key-arr[min])*(max-min)/(arr[max]-[min])
插值查找-重要
在介绍插值查找之前，先考虑一个问题：
为什么二分查找算法一定要是折半，而不是折四分之一或者折更多呢？
其实就是因为方便，简单，但是如果能在二分查找的基础上，让中间的mid点，尽可能靠近想要查找的元素，那不就能提高查找的效率了吗？
二分查找中查找点计算如下：
mid=(low+high)/2, 即mid=low+1/2*(high-low);
可以将查找的点改进为如下：
mid=low+(key-a[low])/(a[high]-a[low])*(high-low)，
这样，让mid值的变化更靠近关键字key，这样也就间接地减少了比较次数。
基本思想：基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，差值查找也属于有序查找。
细节：对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择。
代码跟二分查找类似，只要修改一下mid的计算方式即可。
mid=min+(key-arr[min])*(max-min)/(arr[max]-[min])
斐波那契查找
基本思想：也是二分查找的一种提升算法，通过运用黄金比例的概念在数列中选择查找点进行查找，提高查找效率。同样地，斐波那契查找也属于一种有序查找算法。
斐波那契查找也是在二分查找的基础上进行了优化，优化中间点mid的计算方式即可
mid=min+黄金分割点左半边长度-1
0.618
代码示例：
public class FeiBoSearchDemo {
public static int maxSize = 20;
public static void main(String[] args) {
int[] arr = {1, 8, 10, 89, 1000, 1234};
System.out.println(search(arr, 1234));
}
public static int[] getFeiBo() {
int[] arr = new int[maxSize];
arr[0] = 1;
arr[1] = 1;
for (int i = 2; i < maxSize; i++) {
arr[i] = arr[i - 1] + arr[i - 2];
}
return arr;
}
public static int search(int[] arr, int key) {
int low = 0;
int high = arr.length - 1;
//表示斐波那契数分割数的下标值
int index = 0;
int mid = 0;
//调用斐波那契数列
int[] f = getFeiBo();
//获取斐波那契分割数值的下标
while (high > (f[index] - 1)) {
index++;
}
//因为f[k]值可能大于a的长度，因此需要使用Arrays工具类，构造一个新法数组，并指向temp[],不足的部分会使用0补齐
int[] temp = Arrays.copyOf(arr, f[index]);
//实际需要使用arr数组的最后一个数来填充不足的部分
for (int i = high + 1; i < temp.length; i++) {
temp[i] = arr[high];
}
//使用while循环处理，找到key值
while (low <= high) {
mid = low + f[index - 1] - 1;
if (key < temp[mid]) {//向数组的前面部分进行查找
high = mid - 1;
/*
对k--进行理解
1.全部元素=前面的元素+后面的元素
2.f[k]=k[k-1]+f[k-2]
因为前面有k-1个元素没所以可以继续分为f[k-1]=f[k-2]+f[k-3]
即在f[k-1]的前面继续查找k--
即下次循环,mid=f[k-1-1]-1
*/
index--;
} else if (key > temp[mid]) {//向数组的后面的部分进行查找
low = mid + 1;
index -= 2;
} else {//找到了
//需要确定返回的是哪个下标
if (mid <= high) {
return mid;
} else {
return high;
}
}
}
return -1;
}
}
二分查找、插值查找，斐波那契额查询各自的特点
相同点:
- 都是通过不断的缩小范围来查找对应的数据的
- 数据一定要有顺序
不同点:
计算mid的方式不一样
- 二分查找:mid每次都是指向范围的中间位置
- 插值查找:mid尽可能的靠近要查找的数据，但是要求数据尽可能的分布均匀
- 斐波那契额查找:根据黄金分割点来计算mid指向的位置
分块查找-重要
当数据表中的数据元素很多时，可以采用分块查找。
汲取了顺序查找和折半查找各自的优点，既有动态结构，又适于快速查找，分块查找适用于数据较多，但是数据不会发生变化的情况，如果需要一边添加一边查找，建议使用哈希查找
分块查找的过程：
-
需要把数据分成N多小块，块与块之间不能有数据重复的交集。
-
给每一块创建对象单独存储到数组当中
-
查找数据的时候，先在数组查，当前数据属于哪一块
-
再到这一块中顺序查找
分块的原则1:前一块中的最大数据，小于后一块中所有的数据(块内无序，块间有序)
分块的原则2:块数数量一般等于数字的个数开根号。比如:16个数字一般分为4块左右。
核心思路:先确定要查找的元素在哪一块，然后在块内挨个查找。
有规律的数据
public class A03_BlockSearchDemo {
public static void main(String[] args) {
/*
分块查找
核心思想：
块内无序，块间有序
实现步骤：
1.创建数组blockArr存放每一个块对象的信息
2.先查找blockArr确定要查找的数据属于哪一块
3.再单独遍历这一块数据即可
*/
int[] arr = {16, 5, 9, 12,21, 18,
32, 23, 37, 26, 45, 34,
50, 48, 61, 52, 73, 66};
//创建三个块的对象
Block b1 = new Block(21,0,5);
Block b2 = new Block(45,6,11);
Block b3 = new Block(73,12,17);
//定义数组用来管理三个块的对象（索引表）
Block[] blockArr = {b1,b2,b3};
//定义一个变量用来记录要查找的元素
int number = 37;
//调用方法，传递索引表，数组，要查找的元素
int index = getIndex(blockArr,arr,number);
//打印一下
System.out.println(index);
}
//利用分块查找的原理，查询number的索引
private static int getIndex(Block[] blockArr, int[] arr, int number) {
//1.确定number是在那一块当中
int indexBlock = findIndexBlock(blockArr, number);
if(indexBlock == -1){
//表示number不在数组当中
return -1;
}
//2.获取这一块的起始索引和结束索引 --- 30
// Block b1 = new Block(21,0,5); ---- 0
// Block b2 = new Block(45,6,11); ---- 1
// Block b3 = new Block(73,12,17); ---- 2
int startIndex = blockArr[indexBlock].getStartIndex();
int endIndex = blockArr[indexBlock].getEndIndex();
//3.遍历
for (int i = startIndex; i <= endIndex; i++) {
if(arr[i] == number){
return i;
}
}
return -1;
}
//定义一个方法，用来确定number在哪一块当中
public static int findIndexBlock(Block[] blockArr,int number){ //100
//从0索引开始遍历blockArr，如果number小于max，那么就表示number是在这一块当中的
for (int i = 0; i < blockArr.length; i++) {
if(number <= blockArr[i].getMax()){
return i;
}
}
return -1;
}
}
class Block{
private int max;//最大值
private int startIndex;//起始索引
private int endIndex;//结束索引
//构造方法，set/get方法
public String toString() {
return "Block{max = " + max + ", startIndex = " + startIndex + ", endIndex = " + endIndex + "}";
}
}哈希查找
哈希查找是分块查找的进阶版，适用于数据一边添加一边查找的情况。
一般是数组 + 链表的结合体或者是数组+链表 + 红黑树的结合体
在课程中，为了方便理解，所以规定：
-
数组的0索引处存储1~100
-
数组的1索引处存储101~200
-
数组的2索引处存储201~300
-
以此类推
但是实际上，一般不会采取这种方式，因为这种方式容易导致一块区域添加的元素过多，导致效率偏低。
更多的是先计算出当前数据的哈希值，用哈希值跟数组的长度进行计算，计算出应存入的位置，再挂在数组的后面形成链表，如果挂的元素太多而且数组长度过长，也会把链表转化为红黑树，进一步提高效率。
具体的过程，可以参见B站阿玮讲解课程：从入门到起飞。在集合章节详细讲解了哈希表的数据结构。全程采取动画形式讲解，让大家一目了然。
树表查找
本知识点涉及到数据结构：树。
建议先看一下后面阿玮讲解的数据结构，再回头理解。
基本思想：二叉查找树是先对待查找的数据进行生成树，确保树的左分支的值小于右分支的值，然后在就行和每个节点的父节点比较大小，查找最适合的范围。 这个算法的查找效率很高，但是如果使用这种查找方法要首先创建树。
二叉查找树（BinarySearch Tree，也叫二叉搜索树，或称二叉排序树Binary Sort Tree），具有下列性质的二叉树：
1）若任意节点左子树上所有的数据，均小于本身；
2）若任意节点右子树上所有的数据，均大于本身；
二叉查找树性质：对二叉查找树进行中序遍历，即可得到有序的数列。
不同形态的二叉查找树如下图所示：
基于二叉查找树进行优化，进而可以得到其他的树表查找算法，如平衡树、红黑树等高效算法。
具体细节大家可以参见B站阿玮讲解课程：从入门到起飞。在集合章节详细讲解了树数据结构。全程采取动画形式讲解，让大家一目了然。
在此不多做阐述。
不管是二叉查找树，还是平衡二叉树，还是红黑树，查找的性能都比较高
