Функция бинарного поиска в массиве

Задача

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

Пояснение к задаче и алгоритм решения

Двоичный (бинарный) поиск элемента в массиве применим только к отсортированному массиву. Рассмотрим, как осуществляется бинарный поиск в отсортированном по возрастанию массиве.

Допустим, есть массив чисел [1, 3, 7, 8, 15, 16, 19, 20, 30, 32]. Требуется определить, есть ли в нем элемент со значением 8.

  1. Находится середина массива как частное от целочисленного деления количества элементов массива на 2. В данном случае получаем 5.
  2. Сравниваем элемент с пятым индексом с искомым элементом, т.е. сравниваем числа 16 и 8, если индексация идет с нуля. Они не равны друг другу, и 16 больше, чем 8.
  3. Находим середину левой части массива от пятого по индексу элемента. Для этого складываем индекс первого элемента и предыдущий от прежней середины. Если индексация идет с нуля, то получим 0+4 = 4. Далее делим нацело на 2, получаем 2 - это новая середина.
  4. Сравниваем второй по индексу элемент (число 7) и искомый (число 8). Они не равны и 7 меньше, чем 8.
  5. Значит рассматриваем отрезок начиная с третьего индекса до четверного. Его середина (3+4), деленная нацело на 2, равна 3.
  6. Сравниваем третий по индексу элемент с числом 8. Они равны. Значит искомый элемент есть в массиве и находится под третьим индексом.

Теперь рассмотрим ситуацию, когда элемента нет. Допустим требуется найти число 25 в том же массиве.

  1. Первая середина - число 16, что меньше 25-ти.
  2. Вторая середина - (6+10) / 2 = 8. 30 > 25.
  3. Третья середина - (6+7) / 2 = 6 (деление нацело). 19 < 25.
  4. Четвертая середина - (7+7) / 2 = 7. 20 < 25.
  5. Левая граница массива становится больше на 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.

Пример(ы) выполнения программы на языке Pascal

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-м месте.

Исходный код на языке программирования C

#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
   иначе
    знач := середина
  все
кон

Тема

Функции

Уровень сложности

Сложный

Дата публикации