Используйте двоичный поиск, чтобы найти несколько элементов, удовлетворяющих условию в Java [duplicate]

Вам нужно выполнить два бинарных поиска, чтобы найти самый низкий индекс перед диапазономLow и наивысшим индексом после rangeHigh, таким образом вы можете подсчитать дубликаты в пределах диапазона.

Это даст временную сложность o ( 2 log n), поскольку мы дважды выполняем двоичный поиск.

private int searchArrayForNumbersInRange(int[] arr, int start, int end) {
    int leftIndex = searchLeft(arr, start);
    int rightIndex = searchRight(arr, end);
    int count;

    if (leftIndex < 0 || rightIndex < 0)
        return -1;
    if (rightIndex == leftIndex)
        count = 1;
    else {
        count = rightIndex - leftIndex;
    }
    return count;
}

private int searchLeft(int[] arr, int start) {
    int lo = 0;
    int hi = arr.length - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;

        if (arr[mid] == start && arr[mid -1] < start) {
            return mid - 1;
        }

        if (arr[mid] >= start)
            hi = mid - 1;
        else
            lo = mid + 1;
    }

    return -1;
}

private int searchRight(int[] arr, int end) {
    int lo = 0;
    int hi = arr.length -1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;

        if (arr[mid] == end && arr[mid+1] > end)
            return mid;

        if (mid <= end)
            lo = mid + 1;
        else
            hi = mid - 1;
    }

    return -1;
}

Бинарный поиск диапазона для нижней границы и верхняя граница различны. Здесь разные способы имеют разные критерии остановки и шаг возврата.

1. Для нижней границы (левый диапазон) вы можете вызвать следующую функцию, чтобы получить индекс в отсортированном массиве, где значение больше или равным ему, -1.

   int binarySearchForLeftRange(int a[], int length, int left_range)
   {
       if (a[length-1] < left_range)
           return -1;
   
       int low = 0;
       int high = length-1;
   
       while (low<=high)
       {
           int mid = low+((high-low)/2);
   
           if(a[mid] >= left_range)
               high = mid-1;
           else //if(a[mid]<i)
               low = mid+1;
       }
   
       return high+1;
   }
   

2. Для верхней границы (правый диапазон) вы можете вызвать следующую функцию, чтобы получить индекс в отсортированном массиве, где значение меньше или равно ему -1 в противном случае.

   int binarySearchForRightRange(int a[], int length, int right_range)
   {
       if (a[0] > right_range)
           return -1;
   
       int low = 0;
       int high = length-1;
   
       while (low<=high)
       {
           int mid = low+((high-low)/2);
   
           if(a[mid] > right_range)
               high = mid-1;
           else //if(a[mid]<i)
               low = mid+1;
       }
   
       return low-1;
   }
   

3. Наконец, если вы хотите получить количество элементов в этом диапазоне, это легко на основе возвращаемых значений этих двух вышеперечисленных функций.

   int index_left = binarySearchForLeftRange(a, length, left_range);
   int index_right = binarySearchForRightRange(a, length, right_range);
   
   if (index_left==-1 || index_right==-1 || index_left>index_right)
       count = 0;
   else
       count = index_right-index_left+1;
   

Тест: (с дубликатами)

    int a[] = {3,4,4,6,10,15,15,19,23,23,24,30};
    int length = sizeof(arr)/sizeof(arr[0]);

    int left_range = 4;
    int right_range = 23;
    int index_left = binarySearchForLeftRange(a, length, left_range); // will be 1
    int index_right = binarySearchForRightRange(a, length, right_range); // will be 9

    int count; // will be 9
    if (index_left==-1 || index_right==-1 || index_left>index_right)
        count = 0;
    else
        count = index_right-index_left+1;

EDIT: Конечно, вы можете объединить первые две функции в один пропуская один дополнительный флаг, чтобы указать его как нижнюю границу или верхнюю границу, хотя это будет гораздо более ясным, если нет. Ваш выбор!

Если вы не изучаете алгоритм, используйте вместо него стандартные функции:

    Arrays.binarySearch

Вам в первую очередь необходимо первое появление вашего первого элемента (4) и последнего появления последнего (23) и вычитания. Но нет необходимости (4) быть там, поэтому читайте документацию Arrays.binarySearch, он дает вам, где (4) будет.

Если вы ожидаете много (4) с чтобы написать свой собственный binSearch, который возвращает как первый, так и последний индекс:

найти первое появление в индексе i, если есть предыдущий взгляд на i / 2, если есть (4) посмотреть на i / 4 else посмотрите на 3 * i / 4 ...