logo

TechCodeview

Алгоритм бінарного пошуку – ітеративна та рекурсивна реалізація

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

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

вік вікі каушал

Щоб застосувати алгоритм двійкового пошуку:



  • Структура даних повинна бути відсортована.
  • Доступ до будь-якого елемента структури даних займає постійний час.

Алгоритм бінарного пошуку:

У цьому алгоритмі

  • Розділіть область пошуку на дві половини знаходження середнього покажчика середини .

Пошук середнього індексу mid в алгоритмі бінарного пошуку

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

Як працює алгоритм бінарного пошуку?

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

Розглянемо масив arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91} , і мета = 23 .

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

  • Ключ (тобто 23) більший за поточний середній елемент (тобто 16). Область пошуку переміститься вправо.

Алгоритм бінарного пошуку: порівняйте ключ із 16

  • Ключ менший за поточний середній 56. Область пошуку переміщується ліворуч.

Алгоритм бінарного пошуку: порівняйте ключ із 56

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

Алгоритм бінарного пошуку: Ключові збіги з mid

Рекомендована практика Двійковий пошук Спробуйте!

The Алгоритм бінарного пошуку можна реалізувати наступними двома способами

  • Алгоритм ітераційного бінарного пошуку
  • Алгоритм рекурсивного бінарного пошуку

Нижче наведено псевдокоди для підходів.

Алгоритм ітераційного бінарного пошуку:

Тут ми використовуємо цикл while, щоб продовжити процес порівняння ключа та поділу простору пошуку на дві половини.

Реалізація алгоритму ітераційного бінарного пошуку:

C++ 
// C++ program to implement iterative Binary Search #include  using namespace std; // An iterative binary search function. int binarySearch(int arr[], int low, int high, int x) {  while (low <= high) {  int mid = low + (high - low) / 2;  // Check if x is present at mid  if (arr[mid] == x)  return mid;  // If x greater, ignore left half  if (arr[mid] < x)  low = mid + 1;  // If x is smaller, ignore right half  else  high = mid - 1;  }  // If we reach here, then element was not present  return -1; } // Driver code int main(void) {  int arr[] = { 2, 3, 4, 10, 40 };  int x = 10;  int n = sizeof(arr) / sizeof(arr[0]);  int result = binarySearch(arr, 0, n - 1, x);  (result == -1)  ? cout << 'Element is not present in array'  : cout << 'Element is present at index ' << result;  return 0; }>
C 
// C program to implement iterative Binary Search #include  // An iterative binary search function. int binarySearch(int arr[], int low, int high, int x) {  while (low <= high) {  int mid = low + (high - low) / 2;  // Check if x is present at mid  if (arr[mid] == x)  return mid;  // If x greater, ignore left half  if (arr[mid] < x)  low = mid + 1;  // If x is smaller, ignore right half  else  high = mid - 1;  }  // If we reach here, then element was not present  return -1; } // Driver code int main(void) {  int arr[] = { 2, 3, 4, 10, 40 };  int n = sizeof(arr) / sizeof(arr[0]);  int x = 10;  int result = binarySearch(arr, 0, n - 1, x);  (result == -1) ? printf('Element is not present'  ' in array')  : printf('Element is present at '  'index %d',  result);  return 0; }>
Java 
// Java implementation of iterative Binary Search import java.io.*; class BinarySearch {    // Returns index of x if it is present in arr[].  int binarySearch(int arr[], int x)  {  int low = 0, high = arr.length - 1;  while (low <= high) {  int mid = low + (high - low) / 2;  // Check if x is present at mid  if (arr[mid] == x)  return mid;  // If x greater, ignore left half  if (arr[mid] < x)  low = mid + 1;  // If x is smaller, ignore right half  else  high = mid - 1;  }  // If we reach here, then element was  // not present  return -1;  }  // Driver code  public static void main(String args[])  {  BinarySearch ob = new BinarySearch();  int arr[] = { 2, 3, 4, 10, 40 };  int n = arr.length;  int x = 10;  int result = ob.binarySearch(arr, x);  if (result == -1)  System.out.println(  'Element is not present in array');  else  System.out.println('Element is present at '  + 'index ' + result);  } }>
Python 
# Python3 code to implement iterative Binary # Search. # It returns location of x in given array arr def binarySearch(arr, low, high, x): while low <= high: mid = low + (high - low) // 2 # Check if x is present at mid if arr[mid] == x: return mid # If x is greater, ignore left half elif arr[mid] < x: low = mid + 1 # If x is smaller, ignore right half else: high = mid - 1 # If we reach here, then the element # was not present return -1 # Driver Code if __name__ == '__main__': arr = [2, 3, 4, 10, 40] x = 10 # Function call result = binarySearch(arr, 0, len(arr)-1, x) if result != -1: print('Element is present at index', result) else: print('Element is not present in array')>
C# 
// C# implementation of iterative Binary Search using System; class GFG {    // Returns index of x if it is present in arr[]  static int binarySearch(int[] arr, int x)  {  int low = 0, high = arr.Length - 1;  while (low <= high) {  int mid = low + (high - low) / 2;  // Check if x is present at mid  if (arr[mid] == x)  return mid;  // If x greater, ignore left half  if (arr[mid] < x)  low = mid + 1;  // If x is smaller, ignore right half  else  high = mid - 1;  }  // If we reach here, then element was  // not present  return -1;  }  // Driver code  public static void Main()  {  int[] arr = { 2, 3, 4, 10, 40 };  int n = arr.Length;  int x = 10;  int result = binarySearch(arr, x);  if (result == -1)  Console.WriteLine(  'Element is not present in array');  else  Console.WriteLine('Element is present at '  + 'index ' + result);  } }>
Javascript 
// Program to implement iterative Binary Search   // A iterative binary search function. It returns // location of x in given array arr[l..r] is present, // otherwise -1  function binarySearch(arr, x) {   let low = 0;  let high = arr.length - 1;  let mid;  while (high>= низький) { середній = низький + Math.floor((високий - низький) / 2);    // Якщо елемент присутній посередині // сам if (arr[mid] == x) return mid;    // Якщо елемент менший за mid, то // він може бути присутнім у лівому підмасиві, якщо (arr[mid]> x) high = mid - 1;    // Інакше елемент може бути присутнім лише // у правому підмасиві else low = mid + 1;  } // Ми потрапляємо сюди, коли // елемента немає в масиві return -1; } arr =новий масив(2, 3, 4, 10, 40);  х = 10;  n = обр.довжина;  результат = binarySearch(arr, x);   (результат == -1) ? console.log('Елемент відсутній в масиві') : console.log ('Елемент присутній в індексі ' + результат);   // Цей код надано simranarora5sos і rshuklabbb>
PHP 
 // PHP program to implement // iterative Binary Search // An iterative binary search  // function function binarySearch($arr, $low, $high, $x) { while ($low <= $high) { $mid = $low + ($high - $low) / 2; // Check if x is present at mid if ($arr[$mid] == $x) return floor($mid); // If x greater, ignore // left half if ($arr[$mid] < $x) $low = $mid + 1; // If x is smaller,  // ignore right half else $high = $mid - 1; } // If we reach here, then  // element was not present return -1; } // Driver Code $arr = array(2, 3, 4, 10, 40); $n = count($arr); $x = 10; $result = binarySearch($arr, 0, $n - 1, $x); if(($result == -1)) echo 'Element is not present in array'; else echo 'Element is present at index ', $result; // This code is contributed by anuj_67. ?>>
Вихід 
Element is present at index 3>

Часова складність: O(log N)
Допоміжний простір: О(1)

Алгоритм рекурсивного бінарного пошуку:

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

Реалізація алгоритму рекурсивного бінарного пошуку:

C++ 
#include  using namespace std; // A recursive binary search function. It returns // location of x in given array arr[low..high] is present, // otherwise -1 int binarySearch(int arr[], int low, int high, int x) {  if (high>= низький) { int mid = низький + (високий - низький) / 2;  // Якщо елемент присутній посередині // сам if (arr[mid] == x) return mid;  // Якщо елемент менший за mid, тоді // він може бути присутнім у лівому підмасиві, якщо (arr[mid]> x) return binarySearch(arr, low, mid - 1, x);  // Інакше елемент може бути присутнім лише // у правому підмасиві return binarySearch(arr, mid + 1, high, x);  } } // Код драйвера int main() { int arr[] = { 2, 3, 4, 10, 40 };  int запит = 10;  int n = sizeof(arr) / sizeof(arr[0]);  int result = binarySearch(arr, 0, n - 1, запит);  (результат == -1) ? cout<< 'Element is not present in array'  : cout << 'Element is present at index ' << result;  return 0; }>
C 
// C program to implement recursive Binary Search #include  // A recursive binary search function. It returns // location of x in given array arr[low..high] is present, // otherwise -1 int binarySearch(int arr[], int low, int high, int x) {  if (high>= низький) { int mid = низький + (високий - низький) / 2;  // Якщо елемент присутній посередині // сам if (arr[mid] == x) return mid;  // Якщо елемент менший за mid, тоді // він може бути присутнім лише в лівому підмасиві, якщо (arr[mid]> x) return binarySearch(arr, low, mid - 1, x);  // Інакше елемент може бути присутнім лише // у правому підмасиві return binarySearch(arr, mid + 1, high, x);  } // Ми потрапляємо сюди, коли // елемента немає в масиві return -1; } // Код драйвера int main() { int arr[] = { 2, 3, 4, 10, 40 };  int n = sizeof(arr) / sizeof(arr[0]);  int x = 10;  int result = binarySearch(arr, 0, n - 1, x);  (результат == -1) ? printf('Елемент відсутній в масиві') : printf('Елемент присутній в індексі %d', результат);  повернути 0; }>
Java 
// Java implementation of recursive Binary Search class BinarySearch {  // Returns index of x if it is present in arr[low..  // high], else return -1  int binarySearch(int arr[], int low, int high, int x)  {  if (high>= низький) { int mid = низький + (високий - низький) / 2;  // Якщо елемент присутній // у самій середині if (arr[mid] == x) return mid;  // Якщо елемент менший за mid, тоді // він може бути присутнім лише в лівому підмасиві, якщо (arr[mid]> x) return binarySearch(arr, low, mid - 1, x);  // Інакше елемент може бути присутнім лише // у правому підмасиві return binarySearch(arr, mid + 1, high, x);  } // Ми досягаємо сюди, коли елемент відсутній // в масиві return -1;  } // Код драйвера public static void main(String args[]) { BinarySearch ob = new BinarySearch();  int arr[] = { 2, 3, 4, 10, 40 };  int n = arr.length;  int x = 10;  int result = ob.binarySearch(arr, 0, n - 1, x);  if (результат == -1) System.out.println( 'Елемент відсутній в масиві');  else System.out.println( 'Елемент присутній за індексом ' + результат);  } } /* Цей код створено Раджатом Мішрою */>
Python 
# Python3 Program for recursive binary search. # Returns index of x in arr if present, else -1 def binarySearch(arr, low, high, x): # Check base case if high>= low: mid = low + (high - low) // 2 # Якщо елемент присутній у самій середині if arr[mid] == x: return mid # Якщо елемент менший за mid, то він # може бути присутнім лише у лівому підмасиві elif arr[mid]> x: повертає binarySearch(arr, low, mid-1, x) # Інакше елемент може бути присутнім лише # у правому підмасиві else: повертає binarySearch(arr, mid + 1, high, x ) # Елемент відсутній в масиві else: return -1 # Код драйвера if __name__ == '__main__': arr = [2, 3, 4, 10, 40] x = 10 # Результат виклику функції = binarySearch( arr, 0, len(arr)-1, x) if result != -1: print('Елемент присутній в індексі', результат) else: print('Елемент відсутній в масиві')>
C# 
// C# implementation of recursive Binary Search using System; class GFG {  // Returns index of x if it is present in  // arr[low..high], else return -1  static int binarySearch(int[] arr, int low, int high, int x)  {  if (high>= низький) { int mid = низький + (високий - низький) / 2;  // Якщо елемент присутній // у самій середині if (arr[mid] == x) return mid;  // Якщо елемент менший за mid, тоді // він може бути присутнім лише в лівому підмасиві, якщо (arr[mid]> x) return binarySearch(arr, low, mid - 1, x);  // Інакше елемент може бути присутнім лише // у правому підмасиві return binarySearch(arr, mid + 1, high, x);  } // Ми потрапляємо сюди, коли елемент відсутній // у масиві return -1;  } // Код драйвера public static void Main() { int[] arr = { 2, 3, 4, 10, 40 };  int n = arr.Length;  int x = 10;  int result = binarySearch(arr, 0, n - 1, x);  if (результат == -1) Console.WriteLine( 'Елемент відсутній в arrau');  else Console.WriteLine('Елемент присутній в індексі ' + результат);  } } // Цей код створено Sam007.>
Javascript 
// JavaScript program to implement recursive Binary Search // A recursive binary search function. It returns // location of x in given array arr[low..high] is present, // otherwise -1 function binarySearch(arr, low, high, x){  if (high>= low) { let mid = low + Math.floor((high - low) / 2);  // Якщо елемент присутній посередині // сам if (arr[mid] == x) return mid;  // Якщо елемент менший за mid, тоді // він може бути присутнім лише в лівому підмасиві, якщо (arr[mid]> x) return binarySearch(arr, low, mid - 1, x);  // Інакше елемент може бути присутнім лише // у правому підмасиві return binarySearch(arr, mid + 1, high, x);  } // Ми потрапляємо сюди, коли // елемента немає в масиві return -1; } let arr = [ 2, 3, 4, 10, 40 ]; нехай x = 10; let n = arr.length let result = binarySearch(arr, 0, n - 1, x); (результат == -1) ? console.log( 'Елемент відсутній в масиві') : console.log('Елемент присутній в індексі ' +результат);>
PHP 
 // PHP program to implement // recursive Binary Search // A recursive binary search // function. It returns location // of x in given array arr[low..high]  // is present, otherwise -1 function binarySearch($arr, $low, $high, $x) { if ($high>= $low) { $mid = ceil($low + ($high - $low) / 2); // Якщо елемент присутній // у самій середині if ($arr[$mid] == $x) return floor($mid); // Якщо елемент менший за // mid, тоді він // може бути присутнім у лівому підмасиві, якщо ($arr[$mid]> $x) return binarySearch($arr, $low, $mid - 1, $x) ); // Інакше елемент може // бути присутнім лише у правому підмасиві return binarySearch($arr, $mid + 1, $high, $x); } // Ми потрапляємо сюди, коли // елемента немає в масиві return -1; } // Код драйвера $arr = array(2, 3, 4, 10, 40); $n = count($arr); $x = 10; $результат = binarySearch($arr, 0, $n - 1, $x); if(($result == -1)) echo 'Елемент відсутній в масиві'; else echo 'Елемент присутній в індексі ', $result; ?>>
Вихід 
Element is present at index 3>
  • Часова складність:
    • Найкращий випадок: O(1)
    • Середній випадок: O(log N)
    • Найгірший випадок: O(log N)
  • Допоміжний простір: O(1), якщо розглядається стек рекурсивних викликів, тоді допоміжним простором буде O(logN).
  • Бінарний пошук можна використовувати як будівельний блок для більш складних алгоритмів, які використовуються в машинному навчанні, наприклад алгоритмів для навчання нейронних мереж або пошуку оптимальних гіперпараметрів для моделі.
  • Його можна використовувати для пошуку в комп’ютерній графіці, як-от алгоритми трасування променів або відображення текстури.
  • Його можна використовувати для пошуку в базі даних.
  • Двійковий пошук швидший за лінійний, особливо для великих масивів.
  • Більш ефективний, ніж інші алгоритми пошуку з подібною часовою складністю, такі як інтерполяційний пошук або експоненціальний пошук.
  • Двійковий пошук добре підходить для пошуку великих наборів даних, які зберігаються у зовнішній пам’яті, наприклад на жорсткому диску чи в хмарі.
  • Масив слід відсортувати.
  • Двійковий пошук вимагає, щоб шукана структура даних зберігалася в безперервних розташуваннях пам’яті.
  • Двійковий пошук вимагає, щоб елементи масиву були порівнюваними, тобто вони повинні бути впорядковані.

Часті запитання (FAQ) щодо бінарного пошуку:

1. Що таке бінарний пошук?

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

2. Як працює бінарний пошук?

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

3. Яка часова складність двійкового пошуку?

Часова складність двійкового пошуку становить O(log2n), де n – кількість елементів у масиві. Це пояснюється тим, що на кожному кроці розмір інтервалу пошуку зменшується вдвічі.

4. Які передумови для бінарного пошуку?

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

5. Що станеться, якщо масив не відсортовано для бінарного пошуку?

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

6. Чи можна застосувати двійковий пошук до нечислових даних?

Так, двійковий пошук можна застосовувати до нечислових даних, якщо існує певний порядок для елементів. Наприклад, його можна використовувати для пошуку рядків в алфавітному порядку.

7. Які загальні недоліки бінарного пошуку?

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

обрізка рядка javascript

8. Коли слід використовувати бінарний пошук?

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

9. Чи можна двійковий пошук реалізувати рекурсивно?

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

10. Чи завжди двійковий пошук є найкращим вибором для пошуку в сортованому масиві?

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

Пов'язані статті:

  • Двійковий пошук підручника з відповідями із завданнями
  • Лінійний пошук проти бінарного пошуку
  • Як визначити та вирішити проблеми бінарного пошуку?