// 二分查找递归解法
public class 二分查找 {
    public static void main(String[] args) {
        int[] arr = {3,5,5,6};
        System.out.println(binarySearch(arr,0,arr.length-1,11));
        System.out.println(binarySearch1(arr, 11));
        // 第一个大于等于key
        // 如果找不到当前值会返回大于它的第一个值，如果当前值已经大于所有数组值则返回最后一位下标+1
        System.out.println(lowerbound(arr, 4));
        // 第一个大于key
        // 如果当前值已经大于所有数组值则返回数组最后一位下标+1
        System.out.println(upperbound(arr, 4));
    }
    // 传入的数组必须是升序
    // 递归实现二分查找
    static int binarySearch(int[] arr, int low, int high, int key){
        if(low > high){
            // 没找到
            return -1;
        }
        int mid = (high + low) / 2;
        int midVal = arr[mid];
        if(midVal < key){
            return binarySearch(arr, mid+1, high, key);
        }else if(midVal > key){
            return binarySearch(arr, low, mid-1, key);
        }else{
            // 找到了
            return mid;
        }
    }
    // 迭代实现二分查找
    static int binarySearch1(int[] arr, int key){
        int begin = 0;
        int end = arr.length - 1;
        while(begin <= end){
            int mid = (begin + end) / 2;
            if(arr[mid] == key){
                return mid;
            }else if(arr[mid] > key){
                end = mid - 1;
            }else if(arr[mid] < key){
                begin = mid + 1;
            }
        }
        // 没找到
        return -1;
    }
    // 迭代实现二分查找：第一个大于等于key的数下标，找不到就返回数组最后一个元素的下一个下标
    static int lowerbound(int[] arr, int key){
        int begin = 0;
        int end = arr.length - 1;
        while(begin <= end){
            int mid = (begin + end) / 2;
            if(arr[mid] < key){
                begin = mid + 1;
            }else{
                end = mid - 1;
            }
        }
        return begin;
    }
    // 迭代实现二分查找：第一个大于key的数的下标，找不到就返回数组最后一个元素的下一个下标
    static int upperbound(int[] arr, int key){
        int begin = 0;
        int end = arr.length - 1;
        while(begin <= end){
            int mid = (begin + end) / 2;
            if(arr[mid] > key){
                end = mid - 1;
            }else{
                begin = mid + 1;
            }
        }
        return begin;
    }
}