Нахождение всех элементов в массиве

Question

Вопрос, который не могу найти в интернете(что и не странно, ведь многие пользуются готовым методами) - как найти все одинаковые элементы в массиве бинарным поиском? Будет- ли бинарный поиск бинарным если я ограничу его for-ом при найденном первом элементе и "прошагаю" бинарным поиском поднимая левое "дно" до тех пор пока не вернется "нет найденных элементов"?

Или же это можно сделать другим способом не прибегая к for? Подскажите!

Поиск для крайне левого элемента -

public static int binary_search_leftmost(int[] A,int n,int T) {
        int L = 0;
        int R = n;
        while (L < R) {
            int m = ((L + R) / 2);
            if (A[m] < T){
                L = m + 1;
            } else {
                R = m;
            }
        }
        return L;
}
    public static void main(String [] args) {
        int[] arr = {1,2,3,4,5,5,5,5,6,6,6,7,7,7,7,8,8,8,8,9,9,9};
        System.out.println(binary_search_leftmost(arr,17,5));
    }

Дополнение -

static int binarySearchR(String[] arr, String x) 
    { 
        int l = 0, r = arr.length - 1; 
        while (l < r) { 
            int m = l + (r - l) / 2; 

            int res = x.compareTo(arr[m]); 

            if (res == 0) 
                return m; 

            if (res < 0) 
                r = m - 1;

            else
                 l = m + 1; ; 
        } 

        return -1; 
    }

Не понимаю как исправить чтобы находил крайней правый элемент.. если элемента 2, то находит второй, но если элементов 3 и более, то метод все равно находит только второй элемент идущий за первым.. Например: {"aa","aa","aa","aa","bb","bb"} - метод находит элемент с индексом 1, а нужно чтобы находил с индексом 3

Answer 1

public static int BSL(String A[], String key) 
{ 
    int m; 
    int l = 0, r = A.length; 

    while( r > l ) 
    { 
        m = l + (r - l)/2; 

        if( A[m].compareTo(key) < 0 ) 
            l = m + 1; 
        else
            r = m; 
    } 

    return l; 
} 

public static int BSR(String A[], String key) 
{ 
    int l = 0, r = A.length; 
    int m; 

    while( r > l) 
    { 
        m = l + (r - l)/2; 

        if( A[m].compareTo(key) > 0 ) 
            r = m; 
        else
            l = m + 1; 
    } 
    return r - 1; 

}

    public static void main (String[] args) throws java.lang.Exception
    {
       String[] arr = {"aa","aa","bb","bb","bb","cc","cc"};
       int l = BSL(arr, "bb");
       int r = BSR(arr, "bb");
       System.out.println(l);
       System.out.println(r);

    }

ideone

2
4

Чуть более выгодно во втором поиске передавать уже найденный левый край.

БЛОГ НА HUSL

Нахождение всех элементов в массиве

Ответы (1 шт):