二分查找--同样的套路

二分查找--同样的套路

查找左右边界跟普通查找使用统一的边界控制，最简单。

建议按照流程画一下  并记住

public class ErFen {
    
    public static int search(int[] arr, int L, int R, int T){
        while(L <= R){
            int M = L + (R - L) / 2;
            if(arr[M] > T){
                R = M - 1;
                searchL(arr, L, R, T);
            }else if(arr[M] < T){
                L = M + 1;
                searchL(arr, L, R, T);
            }else{
                return M;
            }
        }
        return -1;
    }

    
    public static int searchL(int[] arr, int L, int R, int T){
        while(L <= R){
            int M = L + (R - L) / 2;
            if(arr[M] >= T){
                R = M - 1;
                searchL(arr, L, R, T);
            }
            if(arr[M] < T){
                L = M + 1;
                searchL(arr, L, R, T);
            }
        }
        if((L <= arr.length - 1) && arr[L] == T){
            return L;
        }
        return -1;
    }

    
    public static int searchR(int[] arr, int L, int R, int T){
        while(L <= R){
            int M = L + (R - L) / 2;
            if(arr[M] > T){
                R = M - 1;
                searchR(arr, L, R, T);
            }
            if(arr[M] <= T){
                L = M + 1;
                searchR(arr, L, R, T);
            }
        }
        if((R >= 0) && arr[R] == T){
            return R;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr1 = {1,2,3,4,5};
        int[] arr2 = {1,2,3,3,3,4,4,5};
        System.out.println(searchL(arr2, 0, arr2.length - 1, 4));//普通查找
        System.out.println(searchL(arr2, 0, arr2.length - 1, 4));//找左
        System.out.println(searchR(arr2, 0, arr2.length - 1, 4));//找右
    }
}