1. Огляд
У цій статті ми розглянемо переваги бінарного пошуку перед простим лінійним пошуком та пройдемося по його реалізації в Java.
2. Потреба в ефективному пошуку
Скажімо, ми займаємось винним бізнесом, і мільйони покупців щодня відвідують наш додаток.
За допомогою нашого додатку клієнт може відфільтрувати товари, ціна яких нижча за n доларів, вибрати пляшку з результатів пошуку та додати їх у свою корзину. У нас мільйони користувачів, які щосекунди шукають вина з обмеженням ціни. Результати повинні бути швидкими.
На задній панелі наш алгоритм проводить лінійний пошук по всьому списку вин, порівнюючи обмеження ціни, введені замовником, з ціною кожної пляшки вина у списку.
Потім він повертає товари, ціна яких менша або дорівнює обмеженню ціни. Цей лінійний пошук має часову складність O (n) .
Це означає, що чим більша кількість пляшок вина у нашій системі, тим більше часу це займе. Час пошуку збільшується пропорційно кількості нових товарів.
Якщо ми почнемо зберігати елементи у відсортованому порядку та шукати елементи за допомогою двійкового пошуку, ми можемо досягти складності O (log n) .
При двійковому пошуку час, зайнятий результатами пошуку, природно збільшується із розміром набору даних, але не пропорційно.
3. Бінарний пошук
Простіше кажучи, алгоритм порівнює значення ключа із середнім елементом масиву; якщо вони нерівні, половина, ключем до якої не може бути частина, усувається, а пошук, що залишився, триває до успіху.
Пам'ятайте - ключовим аспектом тут є те, що масив вже відсортований.
Якщо пошук закінчується тим, що решта половини є порожньою, ключа немає в масиві.
3.1. Ітеративні імпл
public int runBinarySearchIteratively( int[] sortedArray, int key, int low, int high) { int index = Integer.MAX_VALUE; while (low <= high) { int mid = (low + high) / 2; if (sortedArray[mid] key) { high = mid - 1; } else if (sortedArray[mid] == key) { index = mid; break; } } return index; }Метод runBinarySearchIteratively бере аргументи sortedArray , ключ & низький і високий індекси sortedArray . Коли метод вперше запускає низький , перший індекс sortedArray дорівнює 0, тоді як high , останній індекс sortedArray, дорівнює його довжині - 1.
Середина є середнім показником sortedArray . Тепер алгоритм працює той час як цикл , порівнявши ключ із значенням масиву середнього показника sortedArray .
3.2. Рекурсивна імпл
Тепер давайте також подивимося на просту, рекурсивну реалізацію:
public int runBinarySearchRecursively( int[] sortedArray, int key, int low, int high) { int middle = (low + high) / 2; if (high < low) { return -1; } if (key == sortedArray[middle]) { return middle; } else if (key < sortedArray[middle]) { return runBinarySearchRecursively( sortedArray, key, low, middle - 1); } else { return runBinarySearchRecursively( sortedArray, key, middle + 1, high); } } RunBinarySearchRecursively метод приймає sortedArray , ключ, з низьким і високими індексами sortedArray .
3.3. Використання масивів. binarySearch ()
int index = Arrays.binarySearch(sortedArray, key); SortedArray і ключ int , який потрібно шукати в масиві цілих чисел, передаються як аргументи до методу binarySearch класу Java Arrays .
3.4. Використання колекцій. binarySearch ()
int index = Collections.binarySearch(sortedList, key); SortedList & Integer ключ , який буде шукати в списку Integer об'єктів, які передаються в якості аргументів BinarySearch методу в Java Collections класу.
3.5. Продуктивність
Чи використовувати рекурсивний або ітераційний підхід для написання алгоритму - це, в основному, питання особистих переваг. Але все ж є кілька моментів, про які нам слід пам’ятати:
1. Рекурсія може бути повільнішою через накладні витрати на підтримку стека і зазвичай займає більше пам'яті
2. Рекурсія не є зручною для стека . Це може спричинити StackOverflowException під час обробки наборів великих даних
3. Рекурсія додає ясності коду, оскільки робить його коротшим у порівнянні з ітераційним підходом
В ідеалі, двійковий пошук буде виконувати меншу кількість порівнянь на відміну від лінійного пошуку великих значень n. При менших значеннях n лінійний пошук може виконуватись краще, ніж двійковий пошук.
Слід знати, що цей аналіз є теоретичним і може змінюватися залежно від контексту.
Крім того, двійковий алгоритм пошуку потребує відсортованого набору даних, який також має свої витрати . Якщо ми використовуємо алгоритм сортування злиття для сортування даних, до нашого коду додається додаткова складність n log n .
Тож спочатку нам потрібно добре проаналізувати наші вимоги, а потім прийняти рішення щодо того, який алгоритм пошуку найбільше відповідав би нашим вимогам.
4. Висновок
Цей підручник продемонстрував реалізацію двійкового алгоритму пошуку та сценарій, коли переважно було б використовувати його замість лінійного пошуку.
Будь ласка, знайдіть код підручника на GitHub.