折半查找

问题描述：给定一个整数X和整数A0，A1，A2......A(n-1)，后者已经预先排序并在内存中，求下标i使得Ai = X ，如果X不在数据中，则返回i = -1。

我们首先可以想到的一种方法就是从左到右遍历，逐个匹配，运行花费线性时间。然而，这样的算法并没有考虑到题目中已经排序的这个事实，所以这种算法不能算是最优解。那么这里就引入了我们的折半查找，每次验证X是否是居中元素，如果是，即为找到；如果X小于居中元素，检查左侧部分；如果X大于居中元素，检查右侧部分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class BinarySearch {
    public static void main(String[] args) {

        String[] str = {"a","b","c","1","2","3"};
        System.out.println(binarySearch(str , "b"));
    }

    public static <String extends Comparable <? super String>> int binarySearch(String[] a,String x){
        int low = 0;
        int high = a.length -1;

        while (low <= high){
            int mid = (low + high) / 2;

            if(a[mid].compareTo(x) < 0){
                low = mid + 1;
            }else if(a[mid].compareTo(x) > 0){
                high = mid -1;
            }else {
                return mid;
            }
        }
        return -1;
    }

}

其中难以理解的地方就是<String extends Comparable <? super String>>。在这里我们变为<T extends Comparable <? super T>>这样的形式进行讲解。

首先我们先看<T extends Comparable < T >> 这里的意思是T必须实现Comparable接口，并且这个接口的类型为T 这样声明T实例之间可以进行比较

再看看<T extends Comparable <? super T>> 这里的意思是T必须实现Comparable接口，而这个接口可以是T或T的任一父类 这样声明T实例与其父类实例之间也可以进行比较

一般来说我们推崇第二种写法，当然我们在平时也很少会写工具类，所以即使不理解也没什么关系