Як реалізувати алгоритм двійкового пошуку в Java без рекурсії

Ітераційна реалізація популярного алгоритму двійкового пошуку для пошуку елемента у відсортованому масиві.

Привіт усім! Я опублікував у своєму блозі багато статей про алгоритми та структуру даних, але ця перша тут. У цій статті ми розглянемо популярні основні алгоритми інтерв’ю.

Так, ви правильно вгадали: вам потрібно реалізувати двійковий пошук на Java, і вам потрібно написати як ітераційний, так і рекурсивний алгоритми двійкового пошуку.

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

Порівняння визначає, чи дорівнює елемент вхідному матеріалу, менше вхідного чи більше вхідного.

Коли порівнюваний елемент дорівнює введеному, пошук зупиняється і, як правило, повертає позицію елемента.

Якщо елемент не дорівнює вхідному, тоді проводиться порівняння, щоб визначити, чи є вхідний елемент меншим чи більшим за елемент.

Залежно від результату алгоритм запускається спочатку, але здійснюється пошук лише у верхній або нижній підмножині елементів масиву.

Якщо вхід не знаходиться в масиві, алгоритм зазвичай видає унікальне значення, що вказує це як -1, або просто викидає RuntimeException в Java, як NoValueFoundException.

Алгоритми двійкового пошуку, як правило, зменшують удвічі кількість елементів для перевірки з кожною послідовною ітерацією, таким чином, локалізуючи даний елемент (або визначаючи його відсутність) за логарифмічним часом.

До речі, якщо ви не знайомі з фундаментальними алгоритмами пошуку та сортування, тоді ви також можете приєднатися до такого курсу, як Структури даних та Алгоритми: глибоке занурення за допомогою Java для вивчення фундаментальних алгоритмів.

Якщо Java не є вашим вибором мови, ви можете знайти більше рекомендацій щодо JavaScript та Python у цьому списку курсів алгоритмів.

До речі, якщо ви віддаєте перевагу книгам, я пропоную вам прочитати вичерпну книгу з алгоритмів, як « Вступ до алгоритмів » Томаса Кормена.

Ось приклад коду, який показує логіку ітеративного двійкового пошуку в 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? (підручник)
  • У чому різниця між алгоритмом сортування на основі Порівняння та Непорівняння? (відповідь)
  • Як реалізувати сортування сегментів у Java? (підручник)
  • Як реалізувати алгоритм двійкового пошуку без рекурсії в Java? (підручник)
  • 50+ Структура даних та курси алгоритмів для програмістів (запитання)

Дякуємо, що прочитали цю статтю. Якщо вам сподобалась ця стаття, поділіться з друзями та колегами. Якщо у вас є пропозиція чи відгук, залиште коментар.

PS - Якщо ви серйозно ставитесь до вдосконалення своїх навичок алгоритмів, я думаю, що для початку найкраще вибрати Структури даних та алгоритми: глибоке занурення за допомогою Java.