package 二分查找;

import java.util.Arrays;

public class BinarySearch {

    public static void main(String[] args) {

        int[] a = { 123, 423, 21, 321, 12, 341, 3213, 42 };
        // The array must be orderly
        Arrays.sort(a);
        for(int x : a) {
            System.out.print(x+" ");
        }
        System.out.println();
        int rank = rank(123, a);
        System.out.println(rank);
    }

    public static int rank(int key, int[] a) {

        int lo = 0;
        int hi = a.length - 1;

        while (lo <= hi) {
            // 被查找的键要么不存在,要么必然存在于a[lo...hi]之中.
            int mid = lo + (hi - lo) / 2;
            if (key < a[mid]) {
                // 如果key小于a数组的一半大小下标中的数据,那么就可以让最大下标hi减小范围至mid-1
                hi = mid - 1;
            } else if (key > a[mid]) {
                // 如果key大于a数组下标的一半中的数据,那么最小下标从mid基础上+1
                lo = mid + 1;
            } else {
                return mid;
            }
        }
        //不存在返回-1
        return -1;

    }

}