Бинарный поиск

Бинарный поиск нужен для быстрого поиска элемента в массиве. При этом можно найти первое или последние вхождение элемента. Для бинарного поиска необходим отсортированный массив.
Сложность такого алгоритма log₂n, n - количество элементов.

Суть алгоритма:

Находим значение элемента в середине массива и сравниваем его с ключом. Если ключ меньше значения середины, то поиск осуществляется в первой половине элементов, иначе — во второй. Действия прекращаются, когда мы находим элемент равный ключу или больше не можем подсчитать значение середины, то есть переменная left > right.

Пример:

Давайте понаблюдаем, как будет выполняться алгоритм на примере. Нам нужно в массиве 1, 2 ... 8 найти число 6.
Первый делом заведем переменные left, right и center - левый, правый и центральный индекс элемента соответственно. Переменные left и right будут обозначать границу поиска, а с центральным элементом будем проводить сравнения.
Шаг 1.
Изначально left = 0, right = размер массива - 1, центральный элемент будем считать как
center = (left + right) / 2.

Так как наш элемент строго больше чем центральный, то меняем значение левой границы на
left = center + 1. Если бы элемент был меньше чем центральный, то поменяли бы значение правой границы на right = center - 1.
Шаг 2.
left = 4, right = 7, center = (left + right) / 2. В этот раз center попадает на элемент равный нашему ключу. На этом моменте мы должны закончить наш поиск.

Мы будем выводить yes, если искомый элемент есть в массиве, иначе no.

Код на СИ:

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
32
33
34
35
36

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
int main() {
	int i, j, key, flag;
	int left, right, center;
	int A[8] = { 1,2,3,4,5,6,7,8 };  // массив из примера
	scanf("%i", &key);  // вводим ключ
 
	// начало бинарного поиска
	flag = 0;
	left = 0;
	right = 7;
	while (left <= right) {
		center = (right + left) / 2;
		if (A[center] == key) {
			flag = 1;
			break;
		}
		if (A[center] >= key) {
			right = center - 1;
		}
		else {
			left = center + 1;
		}
	}
	// конец бинарного поиска
 
	if (flag == 1) {
		printf("yes");
	}
	else {
		printf("no");
	}
	return 0;
}

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

Давайте посмотрим как искать самое правое вхождение элемента. Будем считать, что хотя бы один такой элемент есть в массиве. На нашем примере будем искать число 2.

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

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
int main() {
	int i, j, key, flag;
	int left, right, center;
	int A[8] = { 2,2,2,3,4,6,7,12 };  // неубывающий массив чисел
	scanf("%i", &key);  // вводим ключ
 
	// начало бинарного поиска
	flag = 0;
	left = 0;
	right = 7;
	while (left <= right) {
		center = (right + left) / 2;
		if (A[center] > key) {  
			right = center - 1;
		}
		else {
			left = center + 1;
		}
	}
	// конец бинарного поиска
 
	printf("%i", right);  
	return 0;
}

Чтобы найти самое левое вхождение, нужно изменить условие в строке 16 на A[center] >= key. А в строке 25 нужно выводить не right, а left.