Бинарный поиск в массиве

БИНАРНЫЙ ПОИСК В УПОРЯДОЧЕНОМ ПО ВОЗРАСТАНИЮ МАССИВЕ

Метод бинарного поиска

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

Формулировка задачи: пусть есть упорядоченный по возрастанию массив целых чисел. Нужно определить, содержит ли этот массив некоторое число (образец).

Метод (алгоритм) бинарного поиска реализуется следующим образом:

Сначала образец сравнивается со средним (по номеру) элементом массива (рис. 5.10, а).

Если образец равен среднему элементу, то задача решена.

Если образец больше среднего элемента, то это значит, что искомый элемент расположен ниже среднего элемента (между элементами с номерами sred+1 и niz), и за новое значение ver h принимается sred+ 1 , а значение niz не меняется (рис. 5.10, б).

Если образец меньше среднего элемента, то это значит, что искомый элемент расположен выше среднего элемента (между элементами с номерами verh и sred-1), и за новое значение niz принимается sred-1, а значение verh не меняется (рис. 5.10, в).

Метод бинарного поиска

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

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

Метод (алгоритм) бинарного поиска реализуется следующим образом:

1. Сначала образец сравнивается со средним (по номеру) элементом массива (рис. 5.10, а).

• Если образец равен среднему элементу, то задача решена.
• Если образец больше среднего элемента, то это значит, что искомый элемент расположен ниже среднего элемента (между элементами с номерами sred+1 и niz), и за новое значение verb принимается sred+i, а значение niz не меняется (рис. 5.10, б).
• Если образец меньше среднего элемента, то это значит, что искомый элемент расположен выше среднего элемента (между элементами с номерами verh и sred-1), и за новое значение niz принимается sred-1, а значение verh не меняется (рис. 5.10, в).

a

б

в

Рис. 5.10. Выбор среднего элемента массива при бинарном поиске

Рис. 5.11. Алгоритм бинарного поиска в упорядоченном по возрастанию массиве

2. После того как определена часть массива, в которой может находиться искомый элемент, по формуле (niz-verh) /2+verh вычисляется новое значение sred и поиск продолжается.

Алгоритм бинарного поиска, блок-схема которого представлена на рис. 5.11, заканчивает свою работу, если искомый элемент найден или если перед выполнением очередного цикла поиска обнаруживается, что значение verh больше, чем niz.

После того как определена часть массива, в которой может находиться искомый элемент, по формуле (niz-verh) /2+verh вычисляется новое значение sred и поиск продолжается.

Алгоритм бинарного поиска, блок-схема которого представлена на рис. 5.11, заканчивает свою работу, если искомый элемент найден или если перед выполнением очередного цикла поиска обнаруживается, что значение verh больше, чем niz.

obrazec - образец для поиска

sred- номер среднего

verh- номер верхнего

niz- номер нижнего

naiden- признак совпадений с образцом ( тип boolean – принимает значение true или false)

0 a[sred]obrazec niz=sred-1 niz " width="640"

Sred:=(niz-verh) div 2 +verh

=(9-1) div 2 +1=5

1

-5

2

-1

3

0

4

3

5

13

6

44

7

8

70

75

9

91

verh

13

a[sred]

Verh=sred+1

sred

130

a[sred]obrazec

niz=sred-1

niz

obrazec verh:=sred+1 niz:=sred-1 (verhniz) or naiden " width="640"

read(obrazec);

verh:=1;niz:=n;

naiden:=false;

sred:=(niz-verh) div 2+verh;

a[sred]=obrazec

naiden:=true

a[sred]obrazec

verh:=sred+1

niz:=sred-1

(verhniz) or naiden

niz) or naiden; if naiden then write(sred) else write('no') end. " width="640"

const n=9;

var i,sred,obrazec,niz,verh:integer;

a:array[1..n] of integer;naiden:boolean;

begin

for i:=1 to n do

read(a[i]);

write(‘ введите образец для поиска ');

read(obrazec);

verh:=1;niz:=n;

naiden:=false;

repeat

sred:=(niz-verh) div 2+verh;

if a[sred]=obrazec then naiden:=true else

if obrazec

until (verhniz) or naiden;

if naiden then write(sred) else write('no')

end.