Двоичный поиск

Лекция

Привет, сегодня поговорим про двоичный поиск, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое двоичный поиск , настоятельно рекомендую прочитать все из категории Алгоритмы и теория алгоритмов.

Когда поиск некоторого элемента необходимо осуществить в упорядоченной по возрастанию или убыванию последовательности, тогда применѝм алгоритм двоичного (бинарного) поиска. Метод использует стратегию «разделяй и властвуй», а именно: заданная последовательность делится на две равные части и поиск осуществляется в одной из этих частей, которая потом также делится надвое, и так до тех пор, пока обнаружится наличие искомого элемента или его отсутствие. Использовать эту операцию, уменьшая каждый раз зону поиска вдвое, позволительно лишь исходя из того факта, что элементы последовательности заранее упорядочены. Найдя средний элемент (сделать это, зная число элементов массива, не составит труда), и сравнив его значение с искомым, можно уверено сказать, где относительно среднего элемента находится искомый элемент.

Далее, будем полагать, что элементы массива располагаются в порядке возрастания, поскольку нет существенной разницы, как именно они упорядочены: по возрастанию или убыванию значение. Также обозначим границы зоны поиска через left и right – крайний левый и крайний правый элементы соответственно.

Ход работы алгоритма, разделенный на этапы, выглядит следующим образом:

зона поиска (на первом шаге ей является весь массив) делиться на две равные части, путем определения ее среднего (mid) элемента;
средний элемент сравнивается с искомым (key), результатом этого сравнения будет один из трех случаев:
- key<mid. Крайней правой границей области поиска становится элемент, стоящий перед средним (right ← mid-1);
- key>mid. Крайней левой границей области поиска становится следующий за средним элемент (left ← mid+1);
- key=mid. Значения среднего и искомого элементов совпадают, следовательно элемент найден, работа алгоритма завершается.
если для проверки не осталось ни одного элемента, то алгоритм завершается, иначе выполняется переход к пункту 1.

В таблице ниже представлен конкретный целочисленный массив, и пошаговое выполнение алгоритма бинарного поиска применительно к его элементам. Об этом говорит сайт https://intellect.icu . Для экономии места в таблице left, right и mid заменены на a, b и c.

Имеется последовательность целых чисел, расположенных в порядке возрастания, а также ключ – число 16. Изначально граничными элементами являются элементы с номерами 1 и 9, и значениями 1 и 81. Вычисляется номер среднего элемента, для чего, как правило, используется формула (right+left)/2, либо left+(right-left)/2 (далее, в программах будет использована вторая формула, как наиболее устойчивая к переполнениям). После сравнения оказывается, что искомый элемент меньше среднего, и поэтому последующий поиск осуществляется в левой части последовательности. Алгоритм продолжает выполняться подобным образом, до нахождения на 4 шаге искомого элемента.

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

Код программы на C++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

#include "stdafx.h"
#include <iostream>
using namespace std;
const int N=10;
//двоичный поиск
int BinarySearch(int A[], int key)
{
int left=0, right=N, mid;
while (left<=right)
{
mid=left+(right-left)/2;
if (key<A[mid]) right=mid-1;
else if (key>A[mid]) left=mid+1;
else return mid;
}
return -1;
}
//главная функция
void main()
{
setlocale(LC_ALL,"Rus");
int i, key;
int A[N];
cout<<"Искомый элемент > "; cin>>key; //ввод ключа
cout<<"Исходный массив: ";
for (i=0; i<N; i++) //заполнение и вывод массива
{ A[i]=N*i; cout<<A[i]<<" "; }
if (BinarySearch(A, key)==-1) cout<<"\nЭлемент не найден";
else cout<<"\nНомер элемента: "<<BinarySearch(A, key)+1;
system("pause>>void");
}

Код программы на Pascal:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

program BinSearch;
uses crt;
const N=10;
type Arr=array[1..N] of integer;
var mid, left, right, key, i: integer;
A: Arr;
{двоичный поиск}
function BinarySearch(A: Arr; key: integer): integer;
begin
left:=1; right:=N;
while left<=right do
begin
mid:=left+(right-left) div 2;
if (key<A[mid]) then right:=mid-1
else if (key>A[mid]) then left:=mid+1
else begin BinarySearch:=mid; exit; end;
end;
BinarySearch:=-1;
end;
{основной блок программы}
begin
write('Искомый элемент > '); read(key); {ввод ключа}
write('Исходный массив: ');
for i:=1 to N do {заполнение и вывод массива}
begin A[i]:=N*i; write(A[i], ' '); end;
writeln;
if (BinarySearch(A, key)=-1) then write('Элемент не найден')
else write('Номер элемента: ', BinarySearch(A, key));
end.

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

В случае, когда первое значение mid совпадает с ключом, тогда считается, что алгоритм выполнился за свое лучшее время O(1). В среднем и худшем случае время работы алгоритма составляет O(logn), что значительно быстрее, чем у линейного поиска, требующего линейного времени.

На этом все! Теперь вы знаете все про двоичный поиск, Помните, что это теперь будет проще использовать на практике. Надеюсь, что теперь ты понял что такое двоичный поиск и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Алгоритмы и теория алгоритмов

Из статьи мы узнали кратко, но содержательно про двоичный поиск

Двоичный поиск

Код программы на C++:

Код программы на Pascal:

Комментарии

Оставить комментарий

Алгоритмы и теория алгоритмов

Термины: Алгоритмы и теория алгоритмов