Пользователь вводит число. Сообщить, есть ли оно в массиве, элементы которого расположены по возрастанию значений, а также, если есть, в каком месте находится. При решении задачи использовать бинарный (двоичный) поиск, который оформить в виде отдельной функции.
Двоичный (бинарный) поиск элемента в массиве применим только к отсортированному массиву. Рассмотрим, как осуществляется бинарный поиск в отсортированном по возрастанию массиве.
Допустим, есть массив чисел [1, 3, 7, 8, 15, 16, 19, 20, 30, 32]. Требуется определить, есть ли в нем элемент со значением 8.
- Находится середина массива как частное от целочисленного деления количества элементов массива на 2. В данном случае получаем 5.
- Сравниваем элемент с пятым индексом с искомым элементом, т.е. сравниваем числа 16 и 8, если индексация идет с нуля. Они не равны друг другу, и 16 больше, чем 8.
- Находим середину левой части массива от пятого по индексу элемента. Для этого складываем индекс первого элемента и предыдущий от прежней середины. Если индексация идет с нуля, то получим 0+4 = 4. Далее делим нацело на 2, получаем 2 — это новая середина.
- Сравниваем второй по индексу элемент (число 7) и искомый (число 8). Они не равны и 7 меньше, чем 8.
- Значит рассматриваем отрезок начиная с третьего индекса до четверного. Его середина (3+4), деленная нацело на 2, равна 3.
- Сравниваем третий по индексу элемент с числом 8. Они равны. Значит искомый элемент есть в массиве и находится под третьим индексом.
Теперь рассмотрим ситуацию, когда элемента нет. Допустим требуется найти число 25 в том же массиве.
- Первая середина — число 16, что меньше 25-ти.
- Вторая середина — (6+10) / 2 = 8. 30 > 25.
- Третья середина — (6+7) / 2 = 6 (деление нацело). 19 < 25.
- Четвертая середина — (7+7) / 2 = 7. 20 < 25.
- Левая граница массива становится больше на 1, чем правая. Это «сигнал» о том, что искомого элемента в массиве нет.
Pascal
const N = 20;
type arr = array[1..N] of integer;
var
a: arr;
i: byte;
p,q,e: integer;
function search(var c: arr; elem: integer): byte;
var m,i,j: integer;
begin
m := N div 2;
i := 1;
j := N;
while (c[m] <> elem) and (i <= j) do begin
if elem > c[m] then i := m + 1
else j := m - 1;
m := (i+j) div 2;
end;
if i > j then search := 0
else search := m;
end;
begin
randomize;
p := 1;
q := 4;
for i:=1 to N do begin
a[i] := random(q-p)+p;
p := p + 3;
q := q + 3;
write(a[i],' ');
end;
writeln;
write('Число: ');
readln(e);
i := search(a,e);
if i = 0 then
writeln('Такого числа в массиве нет.')
else
writeln('Число ', e, ' находится на ', i, '-м месте.');
end.
1 6 7 11 15 17 19 23 27 28 31 35 38 40 45 48 50 52 56 59
Число: 43
Такого числа в массиве нет.
1 5 7 10 14 18 20 23 25 29 33 36 38 41 45 48 51 54 57 58
Число: 25
Число 25 находится на 9-м месте.
Язык Си
#include < stdio.h>
#define N 20
int search(int c[], int elem);
main() {
int a[N], i, p, q, e;
srand(time(NULL));
p = 1;
q = 4;
for (i=0; i< N; i++) {
a[i] = rand() % (q - p) + p;
p += 3;
q += 3;
printf("%d ", a[i]);
}
printf("\nЧисло: ");
scanf("%d", &e);
i = search(a,e);
if (i == 0) printf("Такого числа нет.\n");
else printf("Находится на %d-м месте.\n",i);
}
int search(int c[], int elem) {
int m,i,j;
m = N / 2;
i = 0;
j = N-1;
while (c[m] != elem && i <= j) {
if (elem > c[m]) i = m + 1;
else j = m - 1;
m = (i + j) / 2;
}
if (i > j) return 0;
else return m+1;
}
Python
N = 20
def srch(c,e):
m = N // 2
i = 0
j = N-1
while c[m] != e and i <= j:
if e > c[m]:
i = m + 1
else:
j = m - 1
m = (i+j) // 2
if i > j:
return 0
else:
return m+1
from random import random
p = 1
q = 4
a = [0]*N
for i in range(N):
a[i] = int(random() * (q-p))+p
p += 3
q += 3
print(a[i],end=' ')
print()
e = int(input('Число: '))
i = srch(a,e)
if i == 0:
print('Такого числа нет.')
else:
print('Число находится на %d-м месте.' % i)
КуМир
цел таб arr[1:20]
алг
нач
цел i, a, b, e
a := 1
b := 4
нц для i от 1 до 20
arr[i] := int(rand(a,b))
вывод arr[i], " "
a := a + 3
b := b + 3
кц
вывод нс
цел э, номер
ввод э
номер := бинарный_поиск(э)
если номер <> 0 то
вывод "Элемент найден на ", номер, "-м месте"
иначе
вывод "Элемент не найден"
все
кон
алг цел бинарный_поиск(цел элемент)
нач
цел начало, конец, середина
конец := 20
середина := div(конец,2)
начало := 1
нц пока arr[середина] <> элемент и начало <= конец
если элемент > arr[середина] то
начало := середина + 1
иначе
конец := середина - 1
все
середина := div(конец+начало,2)
кц
если начало > конец то
знач := 0
иначе
знач := середина
все
кон