查找
2021-07-31 本文已影响0人
意大利大炮
算法 | 最坏时间 | 最好时间 | 是否原址 |
---|---|---|---|
选择排序 | O(n) | O(1) | 否 |
插入排序 | O(logn) | O(1) | 是 |
线性查找
在无序的数组中找到指定的值。
- 假设有数组int A[n], 要找到值为x的位置。
方法1
- 从左至右遍历数组A。
- 索引值i从0:n。
- 当A[i] = x时,输出i,跳出循环
- 代码
public int linearSearch1(int A[], int n, int x) {
for (int i = 0; ; i ++) {
if (i == n) {
return -1; // 没找到
}
if (A[i] == x) {
return i;
}
}
}
方法2
- 将A[n-1]的值存储到last中,令A[n-1] = x
- 将 i 赋值为 0;
- 只要A[i] != x, 执行: i 自增1
- 将a[n-1]=last;
- 如果i<n-1,或A[n-1]=x, 返回i
- 否则返回-1
public int linearSearch2(int A[], int n, int x) {
int last = A[n-1];
last = x;
int i = 0;
for (; ; i ++) {
if (A[i] == x) {
break;
}
}
A[n - 1] = last;
if (i < n - 1 || last == x) {
return i;
} else {
return -1;
}
}
对比
方法 | 循环次数 | 校验次数 |
---|---|---|
方法1 | n | 2n |
方法2 | n | n + 1 |
二分查找
定义
二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构
查找过程
首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。
时间复杂度
- O(logn)
代码
public static int binarySearch(Integer[] srcArray, int des) {
//定义初始最小、最大索引
int start = 0;
int end = srcArray.length - 1;
//确保不会出现重复查找,越界
while (start <= end) {
//计算出中间索引值
int middle = (end + start)>>>1 ;//防止溢出
if (des == srcArray[middle]) {
return middle;
//判断下限
} else if (des < srcArray[middle]) {
end = middle - 1;
//判断上限
} else {
start = middle + 1;
}
}
//若没有,则返回-1
return -1;
}