实例190 - 泛型化的折半查找法

折半查找法的平均时间复杂度是log2n。

心法领悟190：泛型在数据结构中的应用。

在学习数据结构的过程中，为了理解方便和简化编程，通常都使用整数作为分析的对象。利用Java的泛型机制，只需要将int替换成泛型类型T就可以实现更加通用的算法。这样就不需要再对不同的数据类型编写不同的算法实现。

提示：Java SE API (java.util.Arrays)中已经实现了优化了的折半查找算法，实际编程中推荐大家使用。

package com.mingrisoft.generic;

import java.util.Arrays;

public class BinSearch {
    public static <T extends Comparable<? extends T>>  int search(T[] array, T key) {
        int low = 0;
        int mid = 0;
        int high = array.length;
        System.out.println("被查找的中间值：");
        while (low <= high) {
            mid = (low + high) / 2;
            System.out.print(mid+" ");
            if (key.compareTo(array[mid]) > 0) {
                low = mid + 1;
            } else if (key.compareTo(array[mid]) < 0) {
                high = mid - 1;
            } else {
                System.out.println();
                return mid;
            }
        }
        return -1;
    }
    
    public static void main(String[] args) {
        Integer[] ints = {1,2,3,4,5,6,7,8,9,10};
        System.out.println("数据集合：");
        System.out.println(Arrays.toString(ints));
        System.out.println("元素3所对应的索引序号："+search(ints, 3));
    }
}

 Result：

数据集合：
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
被查找的中间值：
5 2 
元素3所对应的索引序号：2