close

Алгоритм бинарного поиска (Binary Search) в C++ — объяснение, пример и код

Алгоритм бинарного поиска является более эффективным способом поиска определенного элемента в отсортированном списке. В отличие от линейного поиска, который проверяет элементы последовательно, бинарный поиск делит список пополам и сравнивает целевой элемент со средним элементом. Этот процесс повторяется до тех пор, пока целевой элемент не будет найден или диапазон поиска не станет пустым.

Как это работает

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

Пример

Давайте рассмотрим отсортированный список целых чисел и хотим найти число 34 с помощью двоичного поиска.

Отсортированный список: {12, 23, 34, 45, 56, 67, 89, 90}

  1. Начните со всего списка.
  2. Средний элемент: 56(позиция 4). Сравните с 34.
  3. 56 больше 34. Поиск в левой половине.
  4. Новый средний элемент: 23(позиция 1). Сравните с 34.
  5. 23 меньше 34. Поиск в правой половине.
  6. Новый средний элемент: 45(позиция 3). Сравните с 34.
  7. 45 больше 34. Поиск в левой половине.
  8. Новый средний элемент: 34(позиция 2). Цель найдена.

Пример кода на С++ 

#include <iostream>  
#include <vector>  
  
int binarySearch(const std::vector<int>& arr, int target) {  
    int left = 0;  
    int right = arr.size()- 1;  
  
    while(left <= right) {  
        int mid = left +(right- left) / 2;  
  
        if(arr[mid] == target) {  
            return mid;  
        } else if(arr[mid] < target) {  
            left = mid + 1;  
        } else {  
            right = mid- 1;  
        }  
    }  
  
    return -1;  
}  
  
int main() {  
    std::vector<int> numbers = {12, 23, 34, 45, 56, 67, 89, 90};  
    int target = 34;  
  
    int result = binarySearch(numbers, target);  
  
    if(result != -1) {  
        std::cout << "Element " << target << " found at position " << result << std::endl;  
    } else {  
        std::cout << "Element " << target << " not found in the array" << std::endl;  
    }  
  
    return 0;  
}

В данном примере binarySearch функция используется для поиска числа 34 в отсортированном списке целых чисел. Результатом будет позиция 34 в списке(позиции начинаются с 0) или -1, если номер не найден.