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

Двоичный поиск применяют для нахождения элемента 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).

Теперь программа должна обратиться к функции сортировки sort() передав ей сформированный массив и его размер (предусмотреть подсчет числа перестановок).

Функция sort() после завершения работы возвратит отсортированный массив чисел (алгоритмы сортировки получить у преподавателя).

И в заключение вызывается функция бинарного поиска значения Х, вводимого с клавиатуры.

Контрольные вопросы

1. В чем суть метода сортировки обменом и почему его зовут метод «пузырька»?

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

3. Как работают методы быстрой сортировки?

4. Как оценить скорость алгоритмов сортировки?

5. Что представляет из себя двоичный поиск.

ЗАДАНИЕ 5. «ПОЛИЗ»

Цель работы: познакомиться с алгоритмамиработы снелинейными структурами данных