查找算法——折半查找（JAVA）

折半查找

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

---

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

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;
    }

}

其中难以理解的地方就是