查找算法----二分查找、插值查找、斐波那契查找
# 查找算法----二分查找、插值查找、斐波那契查找## 1、二分查找
### 二分查找的思路分析
1. 先确定该数组的中间的下标mid = (left+right)/2
2. 然后让需要查找的数findVal和arr比较
2.1 findVal > arr，说明你要查找的数在md的右边，因此需要递归的向右查找
2.2 findVal < arr【mid】，说明你要查找的数在mid的左边，因此需要递归的向左查找
2.3 findval arr（mid】说明找到，就返回
3. 什么时候我们需要结束递归，
1）找到就信束递归
2）递归完整个数组，仍然没有找到ndVal，也需要结束递归left > right就退出
## 2、二分查找代码实现
```java
package com.yishuai.find;
/**
* @AuThor yishuai
* @description 二分查找法(只能运用在有序的数组等)
* @date 2021/3/24 3:20 下午
*/
public class TwoSearcher {
public static void main(String[] args) {
int[] initial ={1,2,3,4,5,6,7,8,9};
int i = twoSearcher(initial, 0, initial.length - 1, 2);
System.out.println(i);
}
/**
*二分查找
* @Param initial 初始数组
* @param left 左边的索引
* @param right 右边的索引
* @param findVal 被查找的值
* @return
*/
public static int twoSearcher(int[] initial,int left,int right,int findVal){
//当左边的索引已经大于右边了,或者小于数组的最小数，大于数组的最大数，代表找不到了
//左右的索引可以相等，代表只剩下了这一个数
if (left > right || findVal < initial || findVal > initial){
return -1;
}
int mid = (left+right)/2;
if (initial < findVal){
return twoSearcher(initial,mid + 1,right,findVal);
}else if (initial > findVal){
return twoSearcher(initial,left,mid - 1,findVal);
}else {
return mid;
}
}
}
```
## 3、插值查找(自适应查找)
### 插值查找思路分析
> 1)插值查找原理介绍:
>
> 插值查找算法类似于二分查找，不同的是插值查找每次从自适应 mid 处开始查找。
>
> 2)将折半查找中的求 mid 索引的公式 , left 表示左边索引, right 表示右边索引， findVal代表被查找的值
>
> 3）公式 int mid = left + (right – left) * (findVal – arr) / (arr – arr)
## 4、插值查找代码实现
```java
package com.yishuai.find;
/**
* @author yishuai
* @description 插值查找(自适应查找)
* @date 2021/3/24 4:23 下午
*/
public class InsertSearcher {
public static void main(String[] args) {
int[] initial = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int i = insertSearcher(initial, 0, initial.length - 1, 2);
System.out.println(i);
}
/**
*插值查找(自适应查找)
* @param initial 初始数组
* @param left 左边的索引
* @param right 右边的索引
* @param findVal 被查找的值
* @return
*/
private static int insertSearcher(int[] initial, int left, int right, int findVal) {
if (left > right || findVal < initial || findVal > initial){
return -1;
}
//插值查找的特定公式，其他的和二分查找一样
int mid = left + (right-left) * (findVal - initial)/(initial - initial);
if (initial < findVal){
return insertSearcher(initial,mid + 1,right,findVal);
}else if(initial > findVal){
return insertSearcher(initial,left,mid - 1,findVal);
}else {
return mid;
}
}
}
```
## 5、插值查找注意实现
> 1) 对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找, 速度较快.
>
> 2) 关键字分布不均匀的情况下，该方法不一定比折半查找要好
## 6、斐波那契查找(黄金分割法)
有前面两个就够了，感觉用不到这个算法。略，哈哈哈 (define (binSearch2 ls num) (let loop ((l 0) (h (- (length ls) 1)))
(let* ((i (quotient (+ h l) 2)) (inum (list-ref ls i)))
(cond
((eqv? num inum) i)
((eqv? num l) l)
((eqv? num h) h)
二分查找
((> num inum) (loop (inc i) h))
((< num inum) (loop i (dec i)))))) ) xiaolong620 发表于 2021-4-29 17:07
int mid = (left+right)/2; 这要是奇数的话除以2，是不是会有问题呢？
不会有问题，mid是中间值，奇数那就是中间往左边取的，但是右边还是包含了呀
例如1-6，中间值是3，左边取1-2，右边取4-6，小于就取左边，大于就取右边，等于就是3
例如1-7，中间值是4，左边取1-3，右边取5-7，小于就取左边，大于就取右边，等于就是4 数组的值是无序的怎么办？ 谢谢分享 正在学习python，感谢整理分享！ 飘零星夜 发表于 2021-3-24 17:55
数组的值是无序的怎么办？
对无序数组先排序 lhy888xh 发表于 2021-3-24 18:55
对无序数组先排序
排序后，位置就改变了，这样找到的下标，肯定和一起的不一样了，所以我感觉排序后再找就很奇怪 逸帅 发表于 2021-3-24 18:59
排序后，位置就改变了，这样找到的下标，肯定和一起的不一样了，所以我感觉排序后再找就很奇怪
如果要返回下标的话你可以生成一个对应的列表，元素为（val，idx）的pair，然后对val排序，然后按正常二分查找 nj001 发表于 2021-3-24 17:41
(define (binSearch2 ls num) (let loop ((l 0) (h (- (length ls) 1)))
...
6666看懂了，我又行了 二分法除以2的时候 是不是少个取整啊
页:
[1]
2