一.查找
1.基本查找
从0索引开始挨个往后查找
public class BasicSearchDemo1 {
public static void main(String[] args) {
//基本查找：从0索引开始挨个往后查找
int[] arr = {131, 127, 147, 81, 103, 23, 7, 79};
int target = 17;
System.out.println(search(arr, target));
}
public static boolean search(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
return true;
}
}
return false;
}
}2.二分查找/折半查找
前提条件：数组中的数据必须是有序的，可以是从小到大，也可以是从大到小，但是不能是乱的
核心逻辑：每次都会排除一半的查找范围
步骤：
- 1.得到数组的左右边界（min，max）
- 2.得到中间值(min+max)/2 //如果计算值为小数则仅取整数部分
- 3.比较中间值与目标值大小，确定查找范围
- 4.循环2-3，直至min >= max（欲查找值不再数组范围内）或min == target（查找到目标值），跳出循环并返回索引
public class BinarySearchDemo1 {
public static void main(String[] args) {
//二分查找：1.数组必须是有序的
int[] arr = {1, 8, 10, 89, 1000, 1000, 1234};//定义数组
int target = 89;//确定目标值
int index = binarySearch(arr, target);//交给方法来处理
System.out.println(index);
}
public static int binarySearch(int[] arr, int target) {
//确定左右边界
int min = 0;//定义min
int max = arr.length - 1;//定义max
//循环判断
while (true) {
if (min > max) {//但min>max时，说明欲查找值不在数组内
return -1;//返回-1错误值
}
int mid = (min + max) / 2;//确定中间值
if (arr[mid] > target) {//如果中间值mid大于目标值，确定查找范围为左
max = mid - 1;//重新定义max
} else if (arr[mid] < target) {//反之确定查找范围为右
min = mid + 1;//重新定义min
} else {//剩下中间值等于目标值，返回中间值索引，代表查找成功
return mid;
}
//以上重新定义min/max后进入下一个循环会把新的max与min值交由新的循环，然后重新计算mid值再次缩小范围
}
}
}
3.插值查找/斐波那契查找
对于插值查找与斐波那契查找，个人见解是他们是特殊的二分查找，只不过二分查找是取中间值mid，而他们二者是根据欲查找值于数组内的位置取特殊的“中间值”
插值查找
核心公式：
mid = left + ((target - arr[left]) * (right - left)) // (arr[right] - arr[left])
公式解释：
left：当前搜索范围的左边界right：当前搜索范围的右边界target：要查找的目标值arr[left]：左边界处的元素值arr[right]：右边界处的元素值
斐波那契查找
以1：0.618的方式取中间值，mid=min+黄金分割点左半边长度
故二者使用一份示例代码
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;
}
}4.分块查找
其实分块查找也可以用于无序的数组的，不过我正在写他的代码，写完了会补上的分块查找（Block Search）是一种结合了顺序查找和折半查找的混合查找算法，特别适合用于块内无序、块间有序的数据结构。
算法原理
分块查找将数据分为若干块（一般分为数据的总个数开根号个）（感觉最难的是分块），满足：
- 块内无序：每个块内的元素可以是任意顺序
- 块间有序：第i块的所有元素都小于第i+1块的所有元素
- 建立索引：为每个块建立索引，记录块的最大值和起始位置
如：现有数组{16, 5, 9, 12, 21, 18,32, 23, 37, 26, 45, 34,50, 48, 61, 52, 73, 66}，那么根据分块规则可以分为【16，5，9，12】【21，18，32，23】【37，26，45，34】【50，48，61，52】【73，66】但是又因为前一块的最大值要比后面所有数都要大，和最佳分块数，保证块内元素均匀，我们就可以分为【16, 5, 9, 12, 21, 18,】【32, 23, 37, 26, 45, 34,】【50, 48, 61, 52, 73, 66】
算法步骤
- 分块：将数组分成m个块
- 建立索引表：记录每个块的最大值和起始地址
- 查找：
- 先在索引表中确定目标所在的块（折半查找或顺序查找）
- 然后在确定的块内进行顺序查找
示例代码：
public class BlockSearchDemo1 {
public static void main(String[] args) {
// 分块查找：块内无序，块间有序
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类，记录每一块的最大值，起始索引，结束索引
Block b2 = new Block(45, 6, 11);
Block b3 = new Block(73, 12, 17);
Block[] blockArr = { b1, b2, b3 };//在把创建的block对象放进block数组
int num = 61;//定义目标值
int index = getIndex(blockArr, arr, num);//把分块后数组，原数组，目标值交由getIndex方法操作
System.out.println("num在数组中的索引为：" + index);
}
private static int getIndex(Block[] blockArr, int[] arr, int num) {
int index = findIndexBlock(blockArr, num);//交由findIndexBlock方法查找目标值处于哪一区块中
if (index == -1) {
return -1;//目标值不再任何区块
}
int startIndex = blockArr[index].getStartIndex();//得到目标值所在区块起始索引
int endIndex = blockArr[index].getEndIndex();//得到目标值所在区块结束索引
for (int i = startIndex; i <= endIndex; i++) {
if (arr[i] == num) {
return i;//循环遍历区块匹配目标值并返回目标值索引
}
}
return -1;//目标值不再目标区块中，目标值不在当前数组中
}
private static int findIndexBlock(Block[] blockArr, int num) {
//从0索引遍历blockArr，如果num小于max，那么num就在这一块中
for (int i = 0; i < blockArr.length; i++) {
if (num < blockArr[i].getMax()) {
return i;//返回所在区块
}
}
return -1;//目标值不在任何区块
}
static class Block {
private int max;
private int startIndex;
private int endIndex;
public int getMax() {
return max;
}
public void setMax(int max) {
this.max = max;
}
public int getStartIndex() {
return startIndex;
}
public void setStartIndex(int startIndex) {
this.startIndex = startIndex;
}
public int getEndIndex() {
return endIndex;
}
public void setEndIndex(int endIndex) {
this.endIndex = endIndex;
}
public Block() {
}
public Block(int max, int startIndex, int endIndex) {
this.max = max;
this.startIndex = startIndex;
this.endIndex = endIndex;
}
}
}
5.哈希查找
哈希查找是分块查找的进阶版，适用于数据一边添加一边查找的情况。
一般是数组 + 链表的结合体或者是数组+链表 + 红黑树的结合体
但是实际上，我们一般不会采取这种方式，因为这种方式容易导致一块区域添加的元素过多，导致效率偏低。
更多的是先计算出当前数据的哈希值，用哈希值跟数组的长度进行计算，计算出应存入的位置，再挂在数组的后面形成链表，如果挂的元素太多而且数组长度过长，我们也会把链表转化为红黑树，进一步提高效率。（不过我还没学到，就不好介绍了）
6.树表查找
基本思想：二叉查找树是先对待查找的数据进行生成树，确保树的左分支的值小于右分支的值，然后在就行和每个节点的父节点比较大小，查找最适合的范围。 这个算法的查找效率很高，但是如果使用这种查找方法要首先创建树。
二叉查找树（BinarySearch Tree，也叫二叉搜索树，或称二叉排序树Binary Sort Tree），具有下列性质的二叉树：
1）若任意节点左子树上所有的数据，均小于本身；
2）若任意节点右子树上所有的数据，均大于本身；
二叉查找树性质：对二叉查找树进行中序遍历，即可得到有序的数列。（不过我也没学，也不好介绍）
综上，为查找的几个主流的算法，感谢阅读！