Dichotomy and logarithm

Dichotomy ：

Distinguish between two ways of writing ：

（ One ）：target In the closed zone 【left,right】 In the middle of the day ：right Initial value (len - 1),

When （target < arr[mid]） when ,right = mid - 1.（ Because the closed interval must not be taken mid）

（ Two ）：target Close on the left and open on the right 【left,right) In the middle of the day ：right Initial value len,

When （target < arr[mid]） when ,right = mid .（ Because the closed interval may not get mid）

Topic 1 ： stay arr Find the position of the target value in the

 /**
     *  Two points search , Find whether the ordered array contains the given number , If there is a return to this position , No return -1
     *  Stop conditions ： If you find , Find the number stop 
     */
    public static int binarySearch(int[] arr, int target){
        if (arr == null) return -1;
        int left = 0;
        int right = arr.length ; // If target In the left closed right open section ,right The initial value should not -1
        while (left < right){
            int mid = left + ((right - left) >> 1);
            if(arr[mid] > target){
                right = mid;
            }else if(arr[mid] < target){
                left = mid + 1;
            }else{
                return mid;
            }
        }
        return -1;
    }

Topic two ： stay arr Find the leftmost position greater than or equal to the target value in the

 /**
     *  Two points search , Find in an ordered array  >=  Give the leftmost position of the number ( Find the left border )
     *  Stop conditions ： Two points till the end , There are no more numbers in the range 
     */
    public  static int leftest(int[] arr, int target){
        if(arr == null || arr.length < 1) return -1;
        int left = 0;
        int right = arr.length - 1; // If target In the left closed right closed interval ,right The initial value should be accessible len-1
        int leftest = -1;
        while(left <= right){
            int mid = left + ((right - left) >> 1);
            if(target > arr[mid]){
                left = mid + 1;
            }else{
                leftest = mid; //!!!! These two sentences cannot be exchanged , If the area you are looking for does not contain target The boundary value of 
                right = mid - 1;//!!!
            }
        }
        return leftest;
    }

Topic three ： find Unordered array The local minimum in （ Any two adjacent numbers are not equal ）

 /**
     *  In an unordered array , Any two numbers are not equal , Use dichotomy to find any local minimum 
     * 1. 0 Location  < 1 Location （ return 0）
     * 2. N-2 Location  > N-1 Location （ return N-1）
     * 3. i-1 Location  < i Location  < i+1 Location （ return i）
     */
    public static int searchMin(int[] arr){
        if(arr == null || arr.length == 0) return -1;
        int len = arr.length;
        if(arr.length == 1 || arr[0] < arr[1]) return 0;
        if(arr[len - 2] > arr[len - 1]) return len - 1;
        int left = 0;
        int right = len - 1;
        while(left <= right){// At the beginning , Remove the first step and return to 1 In addition to the location , The state must be the trend that the left and right sides converge towards the middle 
            int mid = left + ((right - left) >> 1);
            //mid=0 Only in left and right All for 0 Or the left=0,right=1 when . return 0 When the situation has been the second if Determine the , So only return 1 The situation of the 
            if(mid == 0) return mid + 1;
            // If mid The position of is exactly the local minimum , Go straight back to 
            if(arr[mid - 1] > arr[mid] && arr[mid] < arr[mid + 1]){
                return mid;
            }
            // If the left half contains a local minimum , You don't need to include left and left+1 The relationship between , Because I have judged before （ May have been mid Or the initial judgment ）
            else if(arr[mid] > arr[mid - 1]){
                right = mid - 1;
            }
            // If the right half contains a local minimum + Both the left and right halves contain local minima （ You can find it on both sides ）
            else {
                left = mid + 1;
            }
        }
        return -1;
    }

Optimize the process ： Special data conditions 、 Special problem solving  

Logarithmic apparatus ：

Use scenarios ： Without a test environment , Test whether the method you write is in the right way

The specific methods ： Write your own method and a simple and correct method to run a large number of different data at the same time （ Try a small sample first ）, If the results are consistent , It shows that your method is correct ; If it's not consistent , There may be a problem with your own method , It may also be that there is a problem with the comparison method , Use smaller data debugging at this time , After that, the test is carried out .

Use Math.random obtain A,B The number between closed intervals ——> (int) (Math.random()*(B-A+1)+A)

Take sorting as an example ：

 public static void main(String[] args) {
        int[] arr = new int[]{3,2,1,1,3,6,9,7};
        // Use logarithm to verify the correctness of the method 
        boolean success = true;
        for(int i = 0; i < 50000; i++){
            int[] arr1 = getRandomArr(20, 100);
            int[] arr2 = copyArray(arr1);
            selectSort(arr1);// As a test algorithm 
            bubbleSort(arr2);// As a comparison algorithm 
            if(!isEqual(arr1, arr2)){
               success = false;
               break;
            }
        }
        System.out.println(success ? "success" : "fail");
    }

 /**
     *  The logarithm generates an array of random length and random contents 
     *  Logarithms are used to verify whether their methods are correct , Run a lot of the same random data at the same time with your own method and a simple and correct method , See if the results are the same 
     *  If the same, the method is correct , If not, there is an error , Then narrow the data range and debug , Running 
     */
    public static int[] getRandomArr(int maxSize, int maxValue){
        int[] arr = new int[(int)Math.random()*(maxSize+1)];
        for(int i = 0; i < arr.length; i++){
            arr[i] = ((int)Math.random()*(maxValue+1)) - ((int)Math.random()*(maxValue+1));
        }
        return arr;
    }

    /**
     *  Copy the array , Re open up space 
     * @param org
     * @return
     */
    public static int[] copyArray(int[] org){
        int[] arr = new int[org.length];
        for(int i = 0; i < org.length; i++){
            arr[i] = org[i];
        }
        return arr;
    }

    /**
     *  Compare whether the elements of two arrays are the same 
     * @param arr1
     * @param arr2
     * @return
     */
    public static boolean isEqual(int[] arr1, int[] arr2){
        if(arr1 == null || arr2 == null || arr1.length != arr2.length){
            return false;
        }
        for(int i = 0; i < arr1.length; i++){
            if(arr1[i] != arr2[i]) return false;
        }
        return true;
    }

Originally intended to use a logarithm to verify the local minimum , However, the results of the comparison method cannot be guaranteed to be consistent with the implementation method .

/**
     *  Logarithmic apparatus 
     */

    /**
     *  Generate random length （ Within a given maximum length ） Random content of （ Within a given maximum ） Array 
     * Math.random()——>[0,1)
     * (int) It's rounding down 
     * Use random obtain  A,B  The number between closed intervals  ——> (int) (Math.random()*(B-A+1)+A)
     * @param maxSize:  Length range [0,maxSize]
     * @param maxValue:  Data range [-maxValue,+maxValue]
     * @return
     */
    public static int[] getRandomArr(int maxSize, int maxValue){
        int[] arr = new int[(int)Math.random()*(maxSize+1)];// The length of the array is [0,maxSize]
        for(int i = 0; i < arr.length; i++){
            arr[i] = (int)(Math.random()*(maxValue+1)) - (int)(Math.random()*(maxValue+1));// Array elements in [0,maxValue-1]
        }
        return arr;
    }

    /**
     *  In order to test the logarithm, write it simply 、 High complexity 、 Ensure accurate methods 
     *  A common way to find a local minimum （ However, the first local minimum found by dichotomy and ab initio traversal may not be the same ...）
     * @return
     */
    public static int ordinaryMethod(int[] arr){
        int len = arr.length;
        if(arr == null || arr.length == 0) return -1;
        if(arr.length == 1) return 0;
        if(arr[0] < arr[1]) return 0;
        if(arr[0] > arr[1]) return 1;
        if(arr[len-2] > arr[len - 1]) return len - 1;
        for(int i = 1; i < len - 1; i++){
            if(arr[i] < arr[i-1] && arr[i] < arr[i+1]) return i;
        }
        return -1;
    }