Как найти подмассив между мин и макс

Question

У меня есть отсортированный массив .Lets предположить

{4,7,9,12,23,34,56,78} Учитывая мин и макс я хочу найти элементы в массиве между минимальной и максимальной в эффективным способом.

Cases:min=23 and max is 78 op:{23,34,56,78} 
min =10 max is 65 op:{12,23,34,56} 

min 0 and max is 100 op:{4,7,9,12,23,34,56,78} 

Min 30 max= 300:{34,56,78} 

Min =100 max=300 :{} //empty 

Я хочу, чтобы найти эффективный способ сделать это? Я не спрашиваю код любого алгоритма, который я могу использовать здесь как DP экспоненциальный поиск?

Answer 1

Поскольку он отсортирован, вы можете легко найти наименьший элемент, который больше или равен минимальному желаемому, используя двоичный поиск по всему массиву.

Бинарный поиск в основном уменьшает пространство пополам с каждой итерацией. Учитывая ваш первый пример 10, вы начинаете, как следует с серединой на 12:

0 1 2 3 4 5 6 7 <- index 
4 7 9 12 23 34 56 78 
     ^^ 

Поскольку элемент вы смотрите выше, чем 10, а следующие низкое меньшее, вы его нашли.

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

На том же примере, как упоминалось ранее, вы начинаете с:

3 4 5 6 7 <- index 
12 23 34 56 78 
     ^^ 

Поскольку это меньше, чем 65 и следующий тоже, вам нужно увеличить указатель на полпути 34..78:

3 4 5 6 7 <- index 
12 23 34 56 78 
     ^^ 

и там у вас есть, потому что число меньше, и следующее число больше (чем 65)

Тогда у вас есть начало в стоп-индексы (3 и 6) для извлечения значений.

0 1 2 3 4 5 6 7 <- index 
4 7 9 ((12 23 34 56)) 78 
      ----------- 

Временная сложность алгоритма O(log N). Хотя имейте в виду, что это действительно становится важным только при работе с большими наборами данных. Если ваши наборы данных состоят только из восьми элементов, вы можете также использовать линейный поиск, так как (1) будет легче писать; и (2) временной дифференциал будет неактуальным.

Я стараюсь не беспокоиться о временной сложности, если операции действительно дороги, размер набора данных попадает в тысячи, или мне приходится делать это тысячи раз в секунду.

Answer 2

Поскольку сортируется, это нужно сделать:

List<Integer> subarray = new ArrayList<Integer>(); 

for (int n : numbers) { 
    if (n >= MIN && n <= MAX) subarray.add(n); 
} 

Это O (п), как вы только смотреть на каждый номер один раз.