public class Search {

    /**
     * while循环实现
     */
    public static int binarySearch(int[] array, int target) {
        int low = 0;
        int high = array.length - 1;
        int mid;
        while (low <= high) {
            //防止int溢出
            mid = low + (high - low) / 2;
            if (array[mid] == target) {
                return mid;
            } else if (array[mid] > target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }

    /**
     * 递归实现
     */
    public static int recursionBinarySearch(int[] array, int target, int low, int high) {

        if (target < array[low] || target > array[high] || low > high) {
            return -1;
        }
        int mid = (low + high) / 2;

        if (array[mid] > target) {
            return recursionBinarySearch(array, target, low, mid - 1);
        } else if (array[mid] < target) {
            return recursionBinarySearch(array, target, mid + 1, high);
        } else {
            return mid;
        }
    }
    
    /**
     * 测试
     */
    public static void main(String[] args) {
        int[] array = {1, 3, 5, 7, 9, 11};
        int target = 9;
//        int position = binarySearch(arr, key);
        int position = recursionBinarySearch(array, target, 0, array.length - 1);

        if (position == -1) {
            System.out.println("查找的是" + target + ",序列中没有该数！");
        } else {
            System.out.println("查找的是" + target + ",找到位置为：" + position);
        }
    }
}