Как да приложим двоичен алгоритъм за търсене в Java без рекурсия

Итеративна реализация на популярния двоичен алгоритъм за търсене за намиране на елемент в сортиран масив.

Здравейте всички! Публикувал съм много статии за алгоритми и структура на данните в моя блог, но този е първият тук. В тази статия ще разгледаме популярни фундаментални алгоритми за интервюта.

Да, добре се досетихте: трябва да приложите двоично търсене в Java и трябва да напишете както итеративни, така и рекурсивни двоични алгоритми за търсене.

В компютърните науки бинарното търсене или търсенето с половин интервал е алгоритъм за разделяне и завладяване, който локализира позицията на елемент в сортиран масив. Бинарното търсене работи чрез сравняване на входна стойност със средния елемент на масива.

Сравнението определя дали елементът е равен на входа, по-малък от входа или по-голям от входа.

Когато елементът, който се сравнява, е равен на входа, търсенето спира и обикновено връща позицията на елемента.

Ако елементът не е равен на входа, тогава се прави сравнение, за да се определи дали входът е по-малък или по-голям от елемента.

В зависимост от резултата алгоритъмът започва отново отначало, но само в горната или долната подмножина на елементите на масива.

Ако входът не се намира в масива, алгоритъмът обикновено извежда уникална стойност, показваща това като -1, или просто изхвърля RuntimeException в Java като NoValueFoundException.

Двоичните алгоритми за търсене обикновено намаляват наполовина броя на елементите, които трябва да се проверяват с всяка следваща итерация, като по този начин намират дадения елемент (или определят липсата му) в логаритмично време.

Btw, ако не сте запознати с фундаменталните алгоритми за търсене и сортиране, можете също да се присъедините към курс като Структури на данни и Алгоритми: Дълбоко гмуркане Използване на Java, за да научите основни алгоритми.

Ако Java не е вашият избор на език, можете да намерите повече препоръки за JavaScript и Python в този списък с курсове по алгоритми.

Btw, ако предпочитате книги, предлагам ви да прочетете изчерпателна книга с алгоритми като Въведение в алгоритмите на Томас Х. Кормен.

Ето някои примерни кодове, които показват логиката на итеративното двоично търсене в Java :

Внедряване на двоично търсене в Java

Ето примерна програма за внедряване на двоично търсене в Java. Алгоритъмът се прилага рекурсивно. Също така, интересен факт, който трябва да се знае за изпълнението на двоично търсене в Java е, че Джошуа Блох, автор на известната книга Effective Java, е написал бинарното търсене в „java.util.Arrays“.

import java.util.Arrays;import java.util.Scanner;
/** * Java program to implement Binary Search. We have implemented Iterative* version of Binary Search Algorithm in Java** @author Javin Paul*/
public class IterativeBinarySearch {
 public static void main(String args[]) { int[] list = new int[]{23, 43, 31, 12}; int number = 12; Arrays.sort(list); System.out.printf("Binary Search %d in integer array %s %n", number, Arrays.toString(list));
 binarySearch(list, 12); System.out.printf("Binary Search %d in integer array %s %n", 43, Arrays.toString(list));
 binarySearch(list, 43); list = new int[]{123, 243, 331, 1298}; number = 331; Arrays.sort(list); System.out.printf("Binary Search %d in integer array %s %n", number, Arrays.toString(list));
 binarySearch(list, 331); System.out.printf("Binary Search %d in integer array %s %n", 331, Arrays.toString(list)); binarySearch(list, 1333);
 // Using Core Java API and Collection framework // Precondition to the Arrays.binarySearch Arrays.sort(list);
 // Search an element int index = Arrays.binarySearch(list, 3);
}
/** * Perform a binary Search in Sorted Array in Java * @param input * @param number * @return location of element in array */
public static void binarySearch(int[] input, int number) {int first = 0;int last = input.length - 1;int middle = (first + last) / 2;
while (first <= last) { if (input[middle] < number) { first = middle + 1;} else if (input[middle] == number) {
System.out.printf(number + " found at location %d %n", middle);break;} else { last = middle - 1;}
middle = (first + last) / 2;
}
if (first > last) { System.out.println(number + " is not present in the list.\n");}
}
}
OutputBinary Search 12 in integer array [12, 23, 31, 43]12 found at location 0Binary Search 43 in integer array [12, 23, 31, 43]43 found at location 3Binary Search 331 in integer array [123, 243, 331, 1298]331 found at location 2Binary Search 331 in integer array [123, 243, 331, 1298]1333 is not present in the list.

Това е всичко за това как да приложите двоично търсене, използвайки рекурсия в Java . Заедно с линейното търсене, това са два от основните алгоритми за търсене, които научавате в класа си по компютърни науки.

Структурата на данните от бинарното дърво за търсене се възползва от този алгоритъм и подрежда данни в йерархична структура, така че да можете да търсите всеки възел за O (logN) време.

Въпреки това, трябва да запомните, че за да използвате двоично търсене, ви е необходим сортиран списък или масив, така че трябва да вземете предвид и разходите за сортиране, когато обмисляте използването на двоичен алгоритъм за търсене в реалния свят.

По-нататъшно обучение

Структури на данни и алгоритми: дълбоко гмуркане с помощта на Java

Алгоритми и структури от данни - част 1 и 2

Структури на данни в Java 9 от Хайнц Кабуц

10 книги за алгоритми за интервюта

10 Структура на данните и курсове по алгоритъм за интервюта

5 безплатни курса за изучаване на структурата на данните и алгоритмите

Други уроци за структурата на данните и алгоритмите, които може да ви харесат

  • Как да внедрим алгоритъма Quicksort на място в Java? (урок)
  • Как да приложим двоично дърво за търсене в Java? (решение)
  • Как да приложим Quicksort алгоритъм без рекурсия? (урок)
  • Как да внедрим алгоритъм за сортиране на вмъкване в Java? (урок)
  • Как да приложим алгоритъм за сортиране на балончета в Java? (урок)
  • Каква е разликата между алгоритъм за сортиране, базиран на сравнение и не-сравнение? (отговор)
  • Как да приложим Bucket Sort в Java? (урок)
  • Как да внедря двоичен алгоритъм за търсене без рекурсия в Java? (урок)
  • 50+ Структура на данни и курсове за алгоритми за програмисти (въпроси)

Благодаря, че прочетохте тази статия. Ако харесвате тази статия, моля, споделете с приятели и колеги. Ако имате някакво предложение или обратна връзка, моля, пуснете коментар.

PS - Ако сериозно се занимавате с подобряването на вашите умения за алгоритми, мисля, че структурите за данни и алгоритмите: Deep Dive с помощта на Java е най-добрият за започване.