public class BinarySearch {

    /**
     * 在计算机科学中非常有名的
     * 二分查找法
     * 它的前提是输入的数组必须是有序的
     * 并且需要明确知道数组是升序的还是降序的
     * 否则找出来的值不正确
     * 所以首先要判断数组是否已经有序
     * @param sourceArray
     * @param targetValue
     */
    static public void binarySearch0(int[] sourceArray,int targetValue) {
        //首先要判断一下输入的数组是
        // 升序的还是降序的还是无序的
        //从数学上来讲，数组有序的话，
        // 随着遍历的进行，被遍历到的
        // 元素和数组首元素在数轴上的
        // 距离会越来越大。利用这一点
        // 可以判断数组是否有序。
        int arrayLength = sourceArray.length;
        int valueDistance = 0;
        for (int counter = 0;counter < arrayLength;counter++) {
            if (Math.abs(sourceArray[counter] - sourceArray[0]) >= valueDistance)
                valueDistance = Math.abs(sourceArray[counter] - sourceArray[0]);
            else {
                System.out.println("错误!数组无序,无法使用二分查找法!");
                return;
            }
        }
        //此时已经判定为有序数组，并且升序降序都已经知道了。
        int lowerPointer = 0;
        int higherPointer = sourceArray.length - 1;
        int counter = 0;
        //打印源数组的顺序情况
        if (sourceArray[arrayLength - 1] >= sourceArray[0])
            System.out.println("源数组为升序");
        else System.out.println("源数组为降序");
        //下面是二分查找法的实现
        while (lowerPointer <= higherPointer) {
            counter++;
            int middlePointer = (lowerPointer + higherPointer) / 2;
            if (sourceArray[middlePointer] == targetValue) {
                System.out.println("共比较了" + counter + "次");
                System.out.println("目标值的index:" + middlePointer);
                return;
            } else {
                if (sourceArray[arrayLength - 1] > sourceArray[0]) {
                    //此时为升序
                    if (sourceArray[middlePointer] < targetValue)
                        lowerPointer = middlePointer + 1;
                    else higherPointer = middlePointer - 1;
                } else {
                    //此时为降序
                    if (sourceArray[middlePointer] > targetValue)
                        lowerPointer = middlePointer + 1;
                    else higherPointer = middlePointer - 1;
                }
            }
        }
        System.out.println("共比较了" + counter + "次");
        System.out.println("查无此值");
    }
}