0%

查找算法

查找算法

线性查找

顺序查找

按照顺序遍历与所查找的数进行比较

1
2
3
4
5
6
7
public static int search(int[] arry, int des) {
for (int i = 0; i <= arry.length - 1; i++) {
if (des == arry[i])
return i;
}
return -1;
}

二分查找

二分查找要求元素必须是有顺序的,每次中间值与所要查找的数进行比较

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static int search(int[] arr,int des){
int start = 0;
int end = arr.length - 1;
// start > end 即表示没有找到
while (start <= end){
// 中间索引
int mid = (start + end )/2;
if(arr[mid] == des){
return mid;
} else if(arr[mid] > des){
end = mid - 1;
} else {
start = mid + 1;
}
}

return -1;
}

分块查找

分块查找是顺序查找和二分查找的整合,把一个大的线性表分为若干块,每块中找到一个最大值以及起始索引组成索引表,要求索引表是有序的,块与块之间需要排序,而对于每块内的节点没有排序要求