Двоичный поиск в массиве

Пусть элементы массива Aуже расставлены по возрастанию и требуется найти элемент,

равный x, среди элементов с номерами от Lдо R.. Для этого использую следующую идею: выбираем средний элемент между Lи R , он имеет номер m=(L+R)/2, где деление выполняется нацело. Сравним его с искомым x. Если он равен x, мы нашли то, что искали. Если xменьше

A[m], надо искать дальше между A[L]и A[m], если xбольше A[m], дальше ищем между

A[m]и A[R].

Переменная flagслужит для того, чтобы определить, нашли мы нужный элемент или нет. Если нашли элемент, равный x, надо присвоить этой переменной значение 1 и выйти из цикла.При этом в переменной mостается номер найденного элемента.

Если массив маленький, то скорость двоичного поиска незначительно отличается от ли-

нейного. Представим себе, что размер массива — 1000000 элементов и нужный нам элемент стоит в конце массива (это самый худший вариант для линейного поиска).

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