无序查找就是顺序查找这组数据(无序数据组)中的每个元素,判断要查找的数据元素是否存在。如果查找成功,则返回该元素在数据组中的位置,若查找失败,则返回-1,具体查找代码如下:
2.6.2 有序查找—二分查找
上面是在一个无序的数据组中进行查找,使用了逐个比对的方法。假设现在需要在一个有序的数据组中进行查找,例如,上面案例的数组test在查找前已经进行了排序,在数组中按照升序进行了排列,其形式为{33,123,234,345,456,567,678,789,890,901},难道还用逐个比对的方法进行查找吗?答案是否定的。我们可以采用二分查找的方式进行查找,具体代码如下:
public static int biSeach(int[] a, int elem){
int n = a.length;
//定义低位下标、高位下标、中间位下标
int low = 0, high = n - 1, mid;
//二分查找
while(low <= high){
mid = (low + high)/2;
if(a[mid] == elem){
return mid + 1;//返回数组下标数加1
}else if(a[mid] < elem){
low = mid + 1;
}else{
high = mid - 1;
}
}
return -1;
public static void main(String[] args){
int[] test = {33,123,234,345,456,567,678,789,890,901};
int elem = 234;
int res = biSeach(test, elem);
if(res != -1)
System.out.println("查找成功! 该元素为第" + res + "个元素");
else System.out.println("查找失败! 该元素在数据组中不存在");
}
}
假设数据结构中元素是按升序排列的,将数据结构中间位置记录的数据与要查找数据进行比较,如果两者相等,则查找成功;否则利用中间位置记录将数据结构分成前、后两个子数据结构,如果中间位置记录的数据大于要查找数据,则进一步查找前一子数据结构,否则进一步查找后一子数据结构。重复以上过程,直到找到满足条件的数据,则查找成功,或直到子数据结构不存在为止,此时查找不成功。