Двоичный поиск – это эффективный алгоритм, который можно использовать для поиска положения определенного элемента в отсортированном массиве. Он работает путем многократного деления интервала поиска пополам, пока не будет найден нужный элемент.

В этой статье я попытаюсь объяснить бинарный поиск максимально простым способом.

Ниже приведено пошаговое объяснение того, как работает бинарный поиск.

  1. Поиск начинается со всего списка, который является интервалом поиска.
  2. Средний элемент интервала поиска сравнивается с целевым элементом. Если они равны, поиск успешен и алгоритм возвращает индекс среднего элемента.
  3. Если средний элемент больше целевого, интервал поиска сужается до левой половины списка.
  4. Если средний элемент меньше целевого элемента, интервал поиска сужается до правой половины списка.
  5. Шаги 2–4 повторяются до тех пор, пока не будет найден целевой элемент или не станет ясно, что элемента нет в списке.

Вот пример того, как работает бинарный поиск в списке [12, 23 , 34, 45, 56, 67, 78, 89 , 90], чтобы найти элемент 78

  1. Интервал поиска — весь список [12, 23, 34, 45, 56, 67, 78, 89, 90]. Средний элемент — 45.
  2. Средний элемент меньше целевого элемента, поэтому интервал поиска сужается до правой половины списка [56, 67, 78, 89, 90].
  3. Средний элемент нового интервала поиска — 78.
  4. Средний элемент равен целевому элементу, поэтому поиск успешен, и алгоритм возвращает индекс 6.

Ниже приведен псевдокод, используемый для бинарного поиска.

  1. Установите start в 0 и end в n - 1, где n — длина массива.
  2. Установите mid на среднее значение start и end.
  3. Пока start меньше или равно end:
  4. Если элемент с индексом mid в массиве равен key, вернуть mid.
  5. Если элемент с индексом mid в массиве больше key, установите end в mid - 1.
  6. Если элемент с индексом mid в массиве меньше key, установите start в mid + 1.
  7. Установите mid на среднее значение start и end.
  8. Возврат -1.

Теперь самое сложное, КОД!!!

#include <iostream>
using namespace std;

int binary_search(int arr[], int n, int key)
{

 // we can also add bounds for key so that it stays within the range of the array
 if(key < arr[0] || key > arr[n-1]){
  return -1;
 }
 int start = 0;
 int end = n - 1;
 while (start <= end)
 {
  int mid = (start + end) / 2;   // this line should be inside the while loop because the value of mid changes every time the loop runs and if it is outside the loop then the value of mid will be the same for every iteration of the loop. hence producing infinite loop.
  if (arr[mid] == key)
  {
   return mid;
  }
  else if (arr[mid] > key)
  {
   end = mid - 1;
  }
  else
  {
   start = mid + 1;
  }
 }
 return -1;
}

int main () {
 int arr[] = {12, 23, 34, 45, 56, 67, 78, 89, 90};
 int n = sizeof(arr) / sizeof(int); // This line of code is often used to determine the size of an array when the size of the array is not known at compile time. It can be useful in situations where the size of the array is determined dynamically at runtime, such as when reading in data from a file or user input.
 int key;
 cout << "Enter the key to be searched" << endl;
 cin >> key;
 int index = binary_search(arr, n, key);
 if (index != -1){
  cout << "element found at index " << index << endl;
 }
 else{
  cout << "element not found" << endl;
 }
 return 0;
}

Надеюсь, что эта статья поможет вам разобраться в бинарном поиске.