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

Двоичный поиск применяют для нахождения элемента X в отсортированном массиве a[1..N].

Основная идея заключается в следующем.

Пусть массив отсортирован в порядке убывания:

1) определяем средний элемент массива a[m], где m = (n+1)/2 ;

2) сравниваем его с Х, и если Х=a[m], то поиск на этом заканчивается;

3) если a[m] < Х, то все элементы от m до n отбрасывают;

4) если a[m] > Х, то отбрасывают элементы от 1 до m;

5) таким образом, каждый раз необходимо пересчитывать левую (L) или правую (R) границы, т.е. изначально L=1, R=n (первый шаг); на втором шаге или L=m или R=m т.е. на втором шаге либо левая, либо правая граница поменяет свое значение и т.д.;

6) поиск продолжается до тех пор, пока элемент не будет найден: a[m]=X, либо пока левая и права границы поиска не совпадут: (L==R), т.е. объект Х в массиве отсутствует.

количество операций сравнения, которые необходимы для нахождения элемента в упорядоченном массиве при помощи алгоритма бинарного поиска K=[log₂ N]+1, где квадратные скобки обозначают целую часть числа находящегося в скобках. Алгоритм имеет следующий вид:

flag = «ложь»;

L=0;

R=N-1;

Начало цикла 1: выполнять пока (L ≤ R) и (flag = =«ложь»);

m=(R+L)/2;

если (a[m] = = X)

тогда

flag = «истина»;

иначе

если a[m]> X

тогда

R=m+1;

иначе

L=m-1;

все

все

конец цикла 1

Если (flag= = true) то

печать сообщения: «Элемент Х найден, его номер - m»,

иначе печать: «Элемента Х нет!»,

Варианты заданий

1. Программа должна сформировать случайным образом одномерный целочисленный массив из N чисел в диапазоне от 0 о 99 (значение N – с клавиатуры). Для этого:

• в начале функции main() нужно вызвать стандартную функцию srand(time(NULL)); которая при каждом обращении к ней задает новое стартовое значение для генератора случайных чисел rand() использую для этого текущее системное время компьютера ;

• далее в цикле заполнить массив N – случайными значениями: m[i]=rand()%100; (rand() возвращает очередное псевдослучайное число в диапазоне от 0 до RAND_MAX, обе функции декларированы в заголовочном файле stdlib.h, а time() – в time.h).