二分查找（递归+while）、LIS（动态规划+二分）、 lowerBound、upperBound

二分查找（递归+while）、LIS（动态规划+二分）、

lowerBound、upperBound

/**
     *用while代替递归的二分查找
     * @param array
     * @parram target
     * @return target的位置
     */
    public static int binarySearch(int[] array,int target){

        int low = 0;
        int high = array.length-1;     /**注意！ while时low high初始值定义一次    而后在while中切分（二分）  */
        int middle = 0;

        if(target < array[low] || target > array[high] || array[low] > array[high] ){
            return -1;
        }

        while(low <= high){                /**注意！ 此处比较下标（直到二分到一个数剩下为止）*/
            middle = (low + high)/2;       /**注意！  该middle计算在while内，每次二分middle重新计算*/
            if(target < array[middle]){
                high = middle-1;
            }else if(target > array[middle]){
                low = middle+1;
            }else {
                return middle;
            }
        }

        //最后仍然未找到则返回-1
        return -1;
    }


    /**
     *用递归的二分查找
     * @param array
     * @parram target
     * @return target的位置
     */
    public static int recursionBinarySearch(int[] array, int target, int low, int high){   /**注意！ 递归时low high传入最新low gigh  而后在递归调用时更新middle+-1  */

        int middle = (low + high)/2;

        if(target < array[low] || target > array[high] || array[low] > array[high] ){
            return -1;
        }

        if(target < array[middle]){

            return recursionBinarySearch(array,target,low,middle-1);      /**注意！ 此处return 递归方法的返回值（最终为middle） */

        }else if(target > array[middle]){                                                    /**效果如while，最终找到target值刚好为middle值，最坏情况为找到最后一个数才找到*/

            return recursionBinarySearch(array,target,middle+1,high);      /**注意！ 此处return 递归方法的返回值（最终为middle） */

        }else {

            return middle;
        }

    }

    //第一个大于等于给定值key的那个数
    public static int lowerBound(int[] nums, int l, int r, int target){
        while(l<r){
            int m = (l+r)/2;
            if(nums[m]>=target) r= m;
            else    l = m +1;
        }
        return l;

    }

    public static int lowerBound2(int[] nums,int l,int r,int target){
        while(l<=r){
            int m = (l+r)/2;
            if(nums[m]>=target) r= m-1;
            else    l = m +1;
        }
        return l;
    }

    //第一个大于给定值key的那个数
    public static int upperBound(int []nums ,int l,int r, int target){
        while(l<r){
            int m = (l+r)/2;
            if(nums[m]<=target) l = m+1;
            else    r = m;
        }
        return l;
    }