Двоичный(бинарный) поиск — алгоритм поиска элемента в отсортированном массиве. Бинарный поиск нашел себе применение в математике и информатике. Возможно, Вы не будете пользоваться алгоритмом двоичного поиска, но знать его принцип работы должны. Двоичный поиск можно использовать только в том случае, если есть массив, все элементы которого упорядочены (отсортированы). Бинарный поиск не используется для поиска максимального или минимального элементов, так как в отсортированном массиве эти элементы содержатся в начале и в конце массива соответственно, в зависимости от тога как отсортирован массив, по возрастанию или по убыванию. Поэтому алгоритм бинарного поиска применим, если необходимо найти некоторый ключевой элемент в массиве. То есть организовать поиск по ключу, где ключ — это определённое значение в массиве. Разработаем программу, в которой объявим одномерный массив, и организуем двоичный поиск.Объявленный массив нужно инициализировать некоторыми значениями, причём так, чтобы эти значения были упорядочены.
// binary_search.cpp: определяет точку входа для консольного приложения.
#include "stdafx.h"
#include <iostream>
using namespace std;
int main(int argc, char* argv[])
{
const int size_array = 10;
int array_[size_array] = {-8, -7, -6, -6, -4, 2, 6, 7, 8, 15 }; // объявление одномерного массива
cout << "array[" << size_array << "] = { ";
for (int counter = 0; counter < size_array; counter++)
{
cout << array_[counter] << " "; // печать элементов одномерного массива array1
}
cout << " }";
int average_index = 0, // переменная для хранения индекса среднего элемента массива
first_index = 0, // индекс первого элемента в массиве
last_index = size_array -1, // индекс последнего элемента в массиве
//--------------------------------------------------------
search_value = 15; // искомое (ключевое) значение
//--------------------------------------------------------
if (last_index == -1) cout << "\narray is empty" << endl; // массив пуст
while (first_index < last_index)
{
average_index = first_index + (last_index - first_index) / 2; // меняем индекс среднего значения
search_value <= array_[average_index] ? last_index = average_index : first_index = average_index + 1; // найден ключевой элемент или нет
}
if ( array_[last_index] == search_value)
cout << "\nvalue is found" << "\nindex = " << last_index << endl;
else
cout << "\nvalue is not found" << endl;
system("pause");
return 0;
}
Итак, в строке 9 объявлена целочисленная переменная константа, которой присвоено значение 10 — размер одномерного массива. Согласно тону хорошего программирования размер статического массива должен задаваться в отдельной переменной, с квалификатором const. В строке 10 объявлен одномерный массив соответствующего размера. Строки 11 — 16 выводят на экран элементы массива с некоторым оформлением. В строках 17 -19 объявляются переменные. которые будут использоваться в алгоритме двоичного поиска В строке 21 объявлена переменная, значение в которой будет искомым. В строка 23 — 33находится алгоритм двоичного поискав массивах. Сначала нужно проверить размер массива, в котором будет искаться ключевое значение, строка 23. Массив может быть нулевого размера, если размер массива больше или равен 1, тогда начинаем искать ключевое значение. Объявление цикла while строки 25 — 29, в цикле организован поиск значения таким образом, что после выхода из цикла индекс найденного значения сохранится в переменной last_index. В телецикла, строка 28 объявлена условная операция ? : , хотя можно было воспользоваться оператором выбора if else. И наконец, в строках 30 — 33 объявлен оператор условного выбора if else, который определяет, говорит о том, было ли найдено искомое значение или нет.
Рассмотрим пошагово, как именно работает алгоритм двоичного поиска в массивах на псевдокоде:
Шаг первый:
проверка условия цикла: 0 < 9 — true
average_index = 0 + (9 — 0) / 2 = 4, значит средний элемент -4
проверка в условной операции 15 <= (-4) — false
значит first_index = 4 + 1 = 5
Шаг второй:
проверка условия цикла: 5 < 9 — true
average_index = 5 + (9 — 5) / 2 = 7, значит средний элемент 7
проверка в условной операции 15 <= 7 — false
значит first_index = 7 + 1 = 8
Шаг третий:
проверка условия цикла: 8 < 9 — true
average_index = 8 + (9 — 8) / 2 = 8 // значит средний элемент 8
проверка в условной операции 15 <= 8 — false
значит first_index = 8 + 1 = 9
Шаг четвёртый:
проверка условия цикла: 9 < 9 — false // выходим из цикла
при этом значение в переменной last_index не менялось, так как искомое значение в последнем элементе массива
Так как, алгоритмы сортировки, нам пока не известны, то массив инициализируем вручную, причём обязательно упорядоченно. В строке 21 указываем искомый элемент массива и запускаем программу (см. Рисунок 2).
Рисунок 2 — Поиск в массивах С++