数据结构和算法基础（3）——查找算法一、顺序查找二、二分查找三、插值查找四、斐波那契查找五、哈希表

159 阅读 0 评论 105 点赞

我是靠谱客的博主冷静曲奇，这篇文章主要介绍数据结构和算法基础（3）——查找算法一、顺序查找二、二分查找三、插值查找四、斐波那契查找五、哈希表，现在分享给大家，希望可以做个参考。

一、顺序查找

顺序查找适合于线性表。顺序查找也称线性查找，属于无序查找算法。时间复杂度O（n）

二、二分查找

数组要有序
元素必须是有序的。对于静态查找表，一次排序后不再变化，折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
	// 找到一个
public static int binarySearch(int[] arr,int left,int right,int searchNum) {
if (left <= right) {
int mid = (left + right)/2;
int midVal = arr[mid];
if (midVal == searchNum) {
return mid;
}else if (midVal > searchNum) {
return binarySearch(arr,left,mid-1,searchNum);
}else if (midVal < searchNum) {
return binarySearch(arr,mid+1,right,searchNum);
}
}
return -1;
}

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
	// 找到所有
public static ArrayList<Integer> binarySearch1(int[] arr, int left, int right, int searchNum) {
if (left <= right) {
System.out.println("~~~~~~~");
int mid = (left + right)/2;
int midVal = arr[mid];
if (midVal == searchNum) {
ArrayList<Integer> integers = new ArrayList<>();
int temp = mid - 1;
while(temp > 0 && arr[temp] == searchNum) {
integers.add(temp);
temp--;
}
integers.add(mid);
temp = mid + 1;
while (temp < arr.length && arr[temp] == searchNum) {
integers.add(temp);
temp++;
}
return integers;
}else if (midVal > searchNum) {
return binarySearch1(arr,left,mid-1,searchNum);
}else if (midVal < searchNum) {
return binarySearch1(arr,mid+1,right,searchNum);
}
}
return new ArrayList<Integer>();
}

三、插值查找

是二分法的升级，二分法每次折半找到中间值。插值查找将有序数组看成线性的，然后通过比例找到可能的点。
数组要有序

复制代码

public static ArrayList<Integer> insertionSearch(int[] arr, int left, int right, int searchNum){
// 防止分母为0
if (arr[left] == arr[right] && arr[left] != searchNum) {
return new ArrayList<Integer>();
} else if (arr[left] == arr[right] && arr[left] == searchNum){
ArrayList<Integer> integers = new ArrayList<>();
while (left <= right) {
integers.add(left);
left++;
}
return integers;
}
if (left <= right && searchNum >= arr[0] && searchNum <= arr.length - 1) {
System.out.println("~~~~~~~");
int mid
= left + (right - left) / (arr[right] - arr[left]) * (searchNum- arr[left]);
if (arr[mid] > searchNum) {
return insertionSearch(arr,left,mid - 1,searchNum);
} else if (arr[mid] < searchNum) {
return insertionSearch(arr,mid + 1,right,searchNum);
} else if (arr[mid] == searchNum) {
int temp = mid - 1;
ArrayList<Integer> result = new ArrayList<>();
while (temp >= 0 && arr[temp] == searchNum) {
result.add(temp);
temp--;
}
result.add(mid);
temp = mid + 1;
while (temp < arr.length && arr[temp] == searchNum) {
result.add(temp);
temp++;
}
return result;
}
}
return new ArrayList<Integer>();
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
	public static ArrayList<Integer> insertionSearch(int[] arr, int left, int right, int searchNum){
// 防止分母为0
if (arr[left] == arr[right] && arr[left] != searchNum) {
return new ArrayList<Integer>();
} else if (arr[left] == arr[right] && arr[left] == searchNum){
ArrayList<Integer> integers = new ArrayList<>();
while (left <= right) {
integers.add(left);
left++;
}
return integers;
}
if (left <= right && searchNum >= arr[0] && searchNum <= arr.length - 1) {
System.out.println("~~~~~~~");
int mid
= left + (right - left) / (arr[right] - arr[left]) * (searchNum- arr[left]);
if (arr[mid] > searchNum) {
return insertionSearch(arr,left,mid - 1,searchNum);
} else if (arr[mid] < searchNum) {
return insertionSearch(arr,mid + 1,right,searchNum);
} else if (arr[mid] == searchNum) {
int temp = mid - 1;
ArrayList<Integer> result = new ArrayList<>();
while (temp >= 0 && arr[temp] == searchNum) {
result.add(temp);
temp--;
}
result.add(mid);
temp = mid + 1;
while (temp < arr.length && arr[temp] == searchNum) {
result.add(temp);
temp++;
}
return result;
}
}
return new ArrayList<Integer>();
}

四、斐波那契查找

斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=1，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）
黄金分割点，是指把一条线段分割为两部分，使其中一部分与全长之比等于另一部分与这部分之比。其比值是一个无理数，用分数表示为(√5-1)/2，取其前三位数字的近似值是0.618。由于按此比例设计的造型十分美丽，因此称为黄金分割，也称为中外比。这个分割点就叫做黄金分割点（golden section ratio），通常用Φ表示。
数组要有序

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
	public static int fibonacciSearch(int[] arr,int search){
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];
}
System.out.println(Arrays.toString(f));;
int low = 0;
int hight = arr.length - 1;
int k = 0;
int mid = 0;
// 找到最接近原数组长度的菲波那切数f[k]。（大于等于）
while(hight > f[k] - 1) {
k++;
}
// 原不足f[k]长度，要补全到f[k]
int[] arrCopy = Arrays.copyOf(arr, f[k]);
while (low <= hight) {
mid = low + f[k-1] - 1;
if (arrCopy[mid] > search) {
hight = mid - 1;
k--;
} else if (arrCopy[mid] < search) {
low = mid +1;
k -=2;
} else if (arrCopy[mid] == search) {
if (mid <= hight) {
return mid;
} else {
return hight;
}
}
}
return -1;
}