1. Общ преглед
В тази статия ще разгледаме предимствата на бинарното търсене пред простото линейно търсене и ще разгледаме неговото внедряване в Java.
2. Нужда от ефективно търсене
Да приемем, че сме в бизнеса с продажба на вино и милиони купувачи посещават нашето приложение всеки ден.
Чрез нашето приложение клиент може да филтрира артикули с цена под n долара, да избере бутилка от резултатите от търсенето и да ги добави в количката си. Имаме милиони потребители, които търсят вина с ценова граница всяка секунда. Резултатите трябва да са бързи.
В бекенда нашият алгоритъм провежда линейно търсене в целия списък с вина, като сравнява ценовия лимит, въведен от клиента с цената на всяка бутилка вино в списъка.
След това връща артикули, чиято цена е по-малка или равна на ценовия лимит. Това линейно търсене има времева сложност на O (n) .
Това означава, че колкото по-голям е броят на бутилките за вино в нашата система, толкова повече време ще отнеме. Времето за търсене се увеличава пропорционално на броя на въведените нови елементи.
Ако започнем да запазваме елементи в сортиран ред и търсим елементи с помощта на двоичното търсене, можем да постигнем сложност на O (log n) .
При двоично търсене времето, необходимо на резултатите от търсенето, естествено се увеличава с размера на набора от данни, но не пропорционално.
3. Двоично търсене
Най-просто казано, алгоритъмът сравнява ключовата стойност със средния елемент на масива; ако те са неравностойни, половината, в която ключът не може да бъде част, се елиминира и търсенето продължава за останалата половина, докато успее.
Не забравяйте - ключовият аспект тук е, че масивът вече е сортиран.
Ако търсенето завърши с останалата половина празна, ключът не е в масива.
3.1. Итеративно Impl
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, докато високият , последният индекс на sortedArray, е равен на дължината му - 1.
В средата е средният индекс на sortedArray . Сега алгоритъмът изпълнява цикъл while, сравнявайки ключа със стойността на масива на средния индекс на sortedArray .
3.2. Рекурсивно Impl
Сега, нека разгледаме и проста, рекурсивна реализация:
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 Колекции клас.
3.5. производителност
Дали да се използва рекурсивен или итеративен подход за писане на алгоритъма е най-вече въпрос на лични предпочитания. Но все пак има няколко точки, с които трябва да сме наясно:
1. Рекурсията може да бъде по-бавна поради режийните разходи за поддържане на стека и обикновено заема повече памет
2. Рекурсията не е удобна за стека . Това може да причини StackOverflowException при обработка на масиви от големи данни
3. Рекурсията добавя яснота към кода, тъй като го прави по-кратък в сравнение с итеративния подход
В идеалния случай бинарното търсене ще извърши по-малък брой сравнения за разлика от линейното търсене на големи стойности на n. При по-малки стойности на n линейното търсене може да се представи по-добре от бинарното търсене.
Трябва да се знае, че този анализ е теоретичен и може да варира в зависимост от контекста.
Също така, двоичният алгоритъм за търсене се нуждае от сортиран набор от данни, който също има своите разходи . Ако използваме алгоритъм за сортиране на сливане за сортиране на данните, към нашия код се добавя допълнителна сложност от n log n .
Така че първо трябва да анализираме добре нашите изисквания и след това да вземем решение кой алгоритъм за търсене ще отговаря най-добре на нашите изисквания.
4. Заключение
Този урок демонстрира изпълнение на двоичен алгоритъм за търсене и сценарий, при който би било за предпочитане да се използва вместо линейно търсене.
Моля, намерете кода за урока на GitHub.