thought

Determines whether a data is in an ordered array. 1. Dichotomy. 2. Check whether the data in the middle of the array equals the target data. Returns true if equal. 3. If the data in the middle of the array is larger than the target data; The target data is in the left half of the data, and the R marker bit is reset to mid-1. 4. If the data in the middle of the array is smaller than the target data; The target data is located in the right half of the data. Reset the L marker bit to mid +1. 5. Repeat.

code

public static boolean exist(int[] arr, int targetNum){ if (arr ==null || arr.length ==0){ return false; } int L = 0; int R = arr.length-1; int mid =0; while (L< R){ mid = L+(R-L) >>1; If (arr[mid] == targetNum){return true; }else if(arr[mid] > targetNum){if(arr[mid] > targetNum){ L = mid+1; L = mid+1; Return arr[L] == targetNum; // prevent L=R. }Copy the code

To upgrade the

In the ordered array, find the leftmost target data subscript for example: 12333345 targetNum =3 Leftmost subscript 2.

code

public static int nearestIndex(int[] arr,int targetNum){ int L = 0; int R = arr.length -1; int index =-1; while (L<= R){ int mid = L+(R-L)>>1; If (arr[mid]>=targetNum){if (arr[mid]>=targetNum){ R = mid-1; }else { L =mid+1; } } return index; }Copy the code

Similarly, find the right-most index of the target data in the array.

code

    public static int nearsetRightIndex(int[] arr,int targetNum){
        int L =0;
        int R = arr.length -1;
        int index =-1;
        while (L<=R){
            int mid = L+(R-L)>>1;
            if (arr[mid]<= targetNum){
                index = mid;
                L = mid+1;
            }else {
                R = mid-1;
            }
        }
        return index;
    }
Copy the code