开篇介绍
大家好，我是 Java 最全面试题库 的提裤姐，明天这篇是数据结构与算法的第七篇，次要介绍查找中的线性表的查找；在后续，会沿着第一篇开篇的常识线路始终总结上来，做到日更！如果我能做到百日百更，心愿你也能够跟着百日百刷，一百天养成一个好习惯。
程序查找
1. 定义：
程序查找是依照序列原有程序对数组进行遍历比拟查问的根本查找算法
2. 原理：
通过遍历数组来寻找值
3. 代码实现：
public static int ordersearch(int[] arry, int des) {
int i = 0;
for (; i <= arry.length - 1; i++) {if (des == arry[i])
return i;
}
return -1;
}二分查找
1. 定义：
分查找也称折半查找（Binary Search），它是一种效率较高的查找办法。然而，折半查找要求线性表必须采纳顺序存储构造，而且表中元素按关键字有序排列
2. 原理：
首先，假如表中元素是按升序排列，将表两头地位记录的关键字与查找关键字比拟，如果两者相等，则查找胜利；否则利用两头地位记录将表分成前、后两个子表，如果两头地位记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。反复以上过程，直到找到满足条件的记录，使查找胜利，或直到子表不存在为止，此时查找不胜利。
3. 代码实现：
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;
}分块查找
1. 定义：
分块查找是折半查找和程序查找的一种改良办法，分块查找因为只要求索引表是有序的，对块内节点没有排序要求，因而特地适宜于节点动态变化的状况。
2. 原理：
分块查找要求把一个大的线性表分解成若干块，每块中的节点能够任意寄存，但块与块之间必须排序。假如是按关键码值非递加的，那么这种块与块之间必须满足已排序要求，实际上就是对于任意的 i，第 i 块中的所有节点的关键码值都必须小于第 i + 1 块中的所有节点的关键码值。此外，还要建设一个索引表，把每块中的最大关键码值作为索引表的关键码值，按块的程序寄存到一个辅助数组中，显然这个辅助数组是按关键码值费递加排序的。查找时，首先在索引表中进行查找，确定要找的节点所在的块。因为索引表是排序的，因而，对索引表的查找能够采纳程序查找或折半查找；而后，在相应的块中采纳程序查找，即可找到对应的节点。
3. 代码实现：
//index 代表索引数组，st2 代表待查找数组，keytype 代表要查找的元素，m 代表每块大小
public static int blocksearch(int[] index,int[]st2,int keytype,int m){int i=shunxusearch(index,keytype); //shunxunsearch 函数返回值为带查找元素在第几块
System.out.println("在第"+i+"块");
if(i>=0){
int j=m*i; // j 为第 i 块的第一个元素下标
int curlen=(i+1)*m;
for(;j<curlen;j++){if(st2[j]==keytype)
return j;
}
}
return -1;
}
public static int shunxusearch(int[]index,int keytype){if(index[0]>keytype){ // 如果第一块中最大元素大于待查找元素
return 0; // 返回 0. 即待查找元素在第 0 块
}
int i=1;
while((index[i-1]<keytype)&&(index[i]>keytype))
return i;
return -1;