二分查找（遞歸+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;
    }