1、查找算法
- 常用的查找算法有
- 线性查找
- 二分查找法
- 插值查找法
- 菲波那契（黄金分割点）查找
- 统一的接口 ```java package com.daijunyi.structure.search;
/**
- @author djy
- @createTime 2022/2/28 下午2:35
@description / public interface Search { /*
- 查找其中一个就行
- @param list
- @param query
@return */ int indexOf(int[] list,int query);
/**
- 找到所有
- @param list
- @param query
- @return */ int[] indexOfAll(int[] list,int query);
}
<a name="Whhr9"></a>## 1、线性查找- 通过遍历从头到尾查找值- 不需要数据是有序的<a name="cdIGF"></a>### 1、线性搜索代码```javapackage com.daijunyi.structure.search.impl;import com.daijunyi.structure.search.Search;/*** @author djy* @createTime 2022/2/28 下午2:31* @description*/public class SeqSearch implements Search {@Overridepublic int indexOf(int[] list, int query) {for (int i=0;i<list.length;i++){if (list[i] == query){return i;}}return -1;}@Overridepublic List<Integer> indexOfAll(int[] list, int query) {ArrayList<Integer> integers = new ArrayList<>();for (int i=0;i<list.length;i++){if (list[i] == query){integers.add(i);}}return null;}}
2、测试
public static void main(String[] args) {
int[] list = {1,2,3,4,4,5,3,6};
Search search = new SeqSearch();
int result = search.indexOf(list, 3);
System.out.println("结果:"+result);
}
输出结果为
结果:22、二分查找法
-
1、思想实现步骤
首先确定该数组的中间的下标mid=(left+right)/2
- 然后让需要查找的数findVal和arr[mid]比较
- findVal > arr[mid],递归向右查找
- findVal<arr[mid]，递归向左查找
- findVal==arr[mid]说明找到，就返回
- 递归退出条件
import com.daijunyi.structure.search.Search;
import java.util.ArrayList; import java.util.Comparator; import java.util.List;
/**
- @author djy
- @createTime 2022/2/28 下午3:03
- @description
*/
public class BinarySearch implements Search {
@Override
public int indexOf(int[] list, int query) {
} /*return search(list, query, 0, list.length-1);- @param list 查询的列表
- @param query 需要被查询的值
- @param left 左边开始角标
- @param right 右边开始角标
- @return
*/
public int search(int[] list, int query, int left, int right) {
if (left > right) {
} int mid = (left + right) / 2; int result = list[mid]; if (query > result) {return -1;
} else if (query < result) {return search(list, query, mid + 1, right);
} else {return search(list, query, left, mid - 1);
} } }return mid;
<a name="YX2SC"></a>
#### 2、多值查找
- 多值查找就是在找到mid的时候，进行向左和向右扫描
```java
package com.daijunyi.structure.search.impl;
import com.daijunyi.structure.search.Search;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
/**
* @author djy
* @createTime 2022/2/28 下午3:03
* @description
*/
public class BinarySearch implements Search {
@Override
public List<Integer> indexOfAll(int[] list, int query) {
return searchAll(list,query,0,list.length-1);
}
/**
*
* @param list 查询的列表
* @param query 需要被查询的值
* @param left 左边开始角标
* @param right 右边开始角标
* @return
*/
public List<Integer> searchAll(int[] list, int query, int left, int right) {
if (left > right) {
return null;
}
int mid = (left + right) / 2;
int result = list[mid];
if (query > result) {
return searchAll(list, query, mid + 1, right);
} else if (query < result) {
return searchAll(list, query, left, mid - 1);
} else {
//向左和向右进行扫描
ArrayList<Integer> integers = new ArrayList<>();
int index = mid-1;
while (index >= 0 && list[index] == query){
integers.add(index);
index--;
}
index = mid+1;
while (index < list.length && list[index] == query){
integers.add(index);
index++;
}
integers.add(mid);
//排序返回
integers.sort(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1-o2;
}
});
return integers;
}
}
}
3、测试
public static void main(String[] args) {
int[] list = {1,2,3,4,5,6,9,10,28,100,100,100,101,103};
// Search search = new SeqSearch();
Search search = new BinarySearch();
int result = search.indexOf(list, 3);
System.out.println("结果:"+result);
List<Integer> integers = search.indexOfAll(list, 100);
for (Integer item:integers){
System.out.println("多个结果查找:"+item);
}
}
结果
结果:2 多个结果查找:9 多个结果查找:10 多个结果查找:113、插值查找法
1、二分查找存在的问题
当我们拥有一个有序的0到100的数时，我们通过查找一个数字1，需要查找至少5次以上才能找到，但是我们这是一个有序的数组，并且值基本都是连续的，所有有没有更好的方式来定位这个二分查找的点呢
2、原理
插值查找算法类似于二分查找，不同的是插值查找每次从自适应mid处开始查找
- 公式
- 换成我们这里公式:int mid = left+(right-left)*(query-list[left])/(list[right]-list[left])
3、代码实现
1、抽取公共接口方法Search
```java package com.daijunyi.structure.search;
import java.util.ArrayList; import java.util.Comparator; import java.util.List;
/**
- @author djy
- @createTime 2022/2/28 下午2:35
@description / public interface Search { /*
- 查找其中一个就行
- @param list
- @param query
@return */ int indexOf(int[] list,int query);
/**
- 找到所有
- @param list
- @param query
@return */ List
indexOfAll(int[] list, int query); /**
- 根据已经查找的中间值进行查找到所有
- @param list 查找的列表
- @param query 需要查找的值
- @param mid 已经确定的中间值
- @return
*/
default ArrayList
getAllByMiddle(int[] list, int query, int mid) { //向左和向右进行扫描 ArrayList integers = new ArrayList<>(); int index = mid-1; while (index >= 0 && list[index] == query){
} index = mid+1; while (index < list.length && list[index] == query){integers.add(index); index--;
} integers.add(mid); //排序返回 integers.sort(new Comparatorintegers.add(index); index++;() {
}); return integers; }@Override public int compare(Integer o1, Integer o2) { return o1-o2; }
}
<a name="TBw6b"></a>
#### 2、实现插值算法
- InterpolationSearch
- 关键性代码：mid = left+(right-left)*(query-list[left])/(list[right]-list[left]);
```java
package com.daijunyi.structure.search.impl;
import com.daijunyi.structure.search.Search;
import java.util.List;
/**
* @author djy
* @createTime 2022/2/28 下午3:48
* @description
*/
public class InterpolationSearch implements Search {
@Override
public int indexOf(int[] list, int query) {
return search(list,query,0,list.length-1);
}
/**
*
* @param list 查询的列表
* @param query 需要被查询的值
* @param left 左边开始角标
* @param right 右边开始角标
* @return
*/
public int search(int[] list, int query, int left, int right) {
if (left > right) {
return -1;
}
int mid = left+(right-left)*(query-list[left])/(list[right]-list[left]);
int result = list[mid];
if (query > result) {
return search(list, query, mid + 1, right);
} else if (query < result) {
return search(list, query, left, mid - 1);
} else {
return mid;
}
}
@Override
public List<Integer> indexOfAll(int[] list, int query) {
return searchAll(list,query,0,list.length-1);
}
public List<Integer> searchAll(int[] list, int query, int left, int right) {
if (left > right) {
return null;
}
int mid = left+(right-left)*(query-list[left])/(list[right]-list[left]);
int result = list[mid];
if (query > result) {
return searchAll(list, query, mid + 1, right);
} else if (query < result) {
return searchAll(list, query, left, mid - 1);
} else {
return getAllByMiddle(list,query,mid);
}
}
}
4、菲波那契（黄金分割点）查找
1、名词
1、什么叫黄金分割点
黄金分割点是指把一条线段分割为两部分，使其中一部分与全长之比等于另一部分与这部分之比。取其前三位数字的近似值是 0.618。由于按此比例设计的造型十分美丽，因此称为黄金分割，也称为中外比。这是一个神奇的数字，会带来意向不大的效果。
2、什么叫斐波那契数列
斐波那契数列{1,1,2,3,5,8,13,21,34,55}发现斐波那契数列的两个相邻数的比例，无限接近 黄金分割值0.618
2、斐波那契(黄金分割法)原理
斐波那契查找原理与前两种相似，仅仅改变了中间结点（mid）的位置，mid不再是中间或插值得到，而是位于黄金分割点附近，即 mid=low+F(k-1)-1（F 代表斐波那契数列），如下图所示
1、对F(k-1)-1的理解
- 由斐波那契数列 F[k]=F[k-1]+F[k-2] 的性质生质，可以得到（F[k]-1）=（F[k-1]-1）+（F[k-2]-1）+1。该式说明：只要顺序表的长度为F[k]-1，则可以将该表分成长度为F[k-1]-1和F[k-2]-1的两段，即如上图所示。从而中间位置为mid=low+F(k-1)-1
- 类似的，每一子段也可以用相同的方式分割
- 但顺序表长度n不一定刚好等于F[k]-1，所以需要将原来的顺序表长度n增加至F[k]-1。这里的k值只要能使得F[k]-1恰好大于或等于n即可，由以下代码得到,顺序表长度增加后，新增的位置（从n+1到F[k]-1位置），都赋为n位置的值即可。
while(n>fib(k)-1) k++;2、应用
1、代码实现查找一个
```java package com.daijunyi.structure.search.impl;
import com.daijunyi.structure.search.Search;
import java.util.Arrays; import java.util.List;
/**
- @author djy
- @createTime 2022/2/28 下午5:00
@description */ public class FibonacciSearch implements Search { @Override public int indexOf(int[] list, int query) {
int left = 0; int right = list.length-1; int[] f = fib(); int k = 0; //得到是第几个斐波那契 while (right > f[k]-1){ k++; } //进行原来数组扩充 int[] tmp = Arrays.copyOf(list,f[k]); //tmp现在里面的最后那些是用0填充的，我们需要改为最高位填充 for (int i=right;i<tmp.length;i++){ tmp[i] = tmp[right]; } //开始查找 while (left <= right){ int mid = left+f[k-1]-1; int result = tmp[mid]; if (query < result){ //向左 right = mid-1; k--; //解释 因为f[k] = f[k-1]+f[k-2] => f[k-2]+f[k-1]=f[k]; 这里我们就可以这样理解 f[k-2] 相当于left f[k-1]相当于right //因为我们是左移动所以我们要把修改right位置 相当于我们要移动到f[k-1] 所以我们要对k-- }else if (query > result){ //向右查找 left = mid+1; k -= 2; //根据上面的解释，我们现在要右移动，所以我们要修改left值，所以我们就移动到f[k-2]所以k-2 }else{ return mid < list.length ? mid : list.length-1; } } return -1;}
/**
- 获取一个斐波那契数列
- @return
*/
public int[] fib(){
int[] fib = new int[20];
fib[0] = 1;
fib[1] = 1;
for (int i= 2;i<fib.length;i++){
} return fib; } }fib[i] = fib[i-1]+fib[i-2];
<a name="ivocE"></a>
#### 2、测试
```java
public static void main(String[] args) {
int[] list = {1, 2, 3, 4, 5, 6, 9, 10, 28, 100, 100, 100, 101, 103};
Search search = new FibonacciSearch();
int result = search.indexOf(list, 3);
System.out.println("结果:" + result);
}
结果
结果:22、哈希表
1、哈希表的介绍
散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
2、结构
数组+链表
- 数组+链表+二叉树
3、代码实现一个简单的HasHTab
1、创建代码HashTab
- put方法
- get方法
remove方法 ```java package com.daijunyi.structure.hash; /**
- @author djy
- @createTime 2022/3/1 下午5:11
@description */ public class HashTab
private int size;
public HashTab() {
super(); this.size = 10; table = new Entry[10];}
public HashTab(int size) {
this.size = size; table = new Entry[size];}
public V put(K key,V value){
if (value == null){ throw new NullPointerException(); } int hash = key.hashCode(); final Entry<K,V>[] tab = table; int index = getIndex(hash); Entry<K, V> kvEntry = tab[index]; //替换逻辑 while (kvEntry != null){ if (kvEntry.hash == hash && kvEntry.key.equals(key)){ //说明是同一个 V old = kvEntry.value; kvEntry.value = value; return old; } kvEntry = kvEntry.next; } //把新的值加到第一个 tab[index] = new Entry(key,value,hash,tab[index]); return null;}
public V get(K key){
if (key == null){ throw new NullPointerException(); } int hash = key.hashCode(); int index = getIndex(hash); Entry<K, V> kvEntry = table[index]; while (kvEntry != null){ if (kvEntry.hash == hash && kvEntry.key.equals(key)){ return kvEntry.value; } kvEntry = kvEntry.next; } return null;}
public V remove(K key){
if (key == null){ throw new NullPointerException(); } int hash = key.hashCode(); int index = getIndex(hash); Entry<K, V> kvEntry = table[index]; if (kvEntry!=null && kvEntry.hash == hash && kvEntry.key.equals(key)){ table[index] = kvEntry.next; return kvEntry.value; } Entry<K,V> tmp = kvEntry; kvEntry = kvEntry.next; while (kvEntry != null){ if (kvEntry.hash == hash && kvEntry.key.equals(key)){ tmp.next = kvEntry.next; return kvEntry.value; } kvEntry = kvEntry.next; tmp = tmp.next; } return null;}
private int getIndex(int hash) {
return (hash & 0x7FFFFFFF) % size;}
private static class Entry
V value; final K key; final int hash; Entry<K,V> next; public Entry(K key, V value,int hash, Entry<K, V> next) { this.value = value; this.key = key; this.hash = hash; this.next = next; }} }
<a name="I9F6s"></a>
### 2、测试
```java
class HashTabMain{
public static void main(String[] args) {
HashTab<String, String> tab = new HashTab<>();
tab.put("123","值2");
tab.put("12","值4");
System.out.println("获取值:"+tab.get("123"));
System.out.println("替换值:"+tab.put("123","值3"));
System.out.println("获取值:"+tab.get("123"));
System.out.println("删除值:"+tab.remove("123"));
System.out.println("再次获取值:"+tab.get("123"));
System.out.println("获取值:"+tab.get("12"));
}
}
3、测试结果
获取值:值2
替换值:值2
获取值:值3
删除值:值3
再次获取值:null
获取值:值4
若有收获，就点个赞吧
0 人点赞
