2.6 查找

  所谓查找，就是在一组数据中判断元素是否存在，或返回元素及其位置。查找的场景分两类，一类是在无序表中进行查找，另一类是在有序表中进行查找。

2.6.1 无序查找

  无序查找就是顺序查找这组数据（无序数据组）中的每个元素，判断要查找的数据元素是否存在。如果查找成功，则返回该元素在数据组中的位置，若查找失败，则返回-1，具体查找代码如下：

public class SeqSeach{
    public static int seqSeach(int[] a, int elem){
        int n = a.length;
        int i = 0;
        while(i < n && a[i] != elem){
            i++;                     //逐个比对，不相同则数组下标数加1
        }
        if (i == n)                     //数组下标数等于数组长度则表明没查到指定的数据元素
        {
            return -1;             //返回-1
        }else{
            return i+1;           //返回数组下标数+1
        } 
    }       
    public static void main(String[] args){
        int[] test = {123,456,789,234,567,890,345,678,901,33};
        int elem = 234;
        int res = seqSeach(test, elem);
        if(res != -1)
            System.out.println("查找成功! 该元素为第" + res + "个元素");
        else  
            System.out.println("查找失败! 该元素在数据组中不存在");
    }
}

  编译、运行上面的代码，程序运行结果如图2.12所示。

图2.12 无序查找

2.6.2 有序查找—二分查找

  上面是在一个无序的数据组中进行查找，使用了逐个比对的方法。假设现在需要在一个有序的数据组中进行查找，例如，上面案例的数组test在查找前已经进行了排序，在数组中按照升序进行了排列，其形式为{33,123,234,345,456,567,678,789,890,901}，难道还用逐个比对的方法进行查找吗？答案是否定的。我们可以采用二分查找的方式进行查找，具体代码如下：

public class BiSeach{
    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("查找失败! 该元素在数据组中不存在");
    }
}

  二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好，其缺点是要求待查数据结构为有序数据结构，且插入、删除困难。因此，二分查找适用于数据不经常变动而查找频繁的有序数据结构。

  假设数据结构中元素是按升序排列的，将数据结构中间位置记录的数据与要查找数据进行比较，如果两者相等，则查找成功；否则利用中间位置记录将数据结构分成前、后两个子数据结构，如果中间位置记录的数据大于要查找数据，则进一步查找前一子数据结构，否则进一步查找后一子数据结构。重复以上过程，直到找到满足条件的数据，则查找成功，或直到子数据结构不存在为止，此时查找不成功。