Двоичный поиск в массиве (среда программирования КуМир)

Тема: 
Массивы

Используя бинарный поиск, осуществить поиск в отсортированном по возрастанию массиве целых чисел введенный пользователем элемент. Сообщить есть ли он там или нет и, если есть, то на какой позиции.

Значение можно искать просто перебирая элементы массива от начала до искомого. Если его не найдется, то мы дойдем до конца массива. Если же элемент, совпадающий с заданным значением, найдется, то поиск можно прервать при его нахождении.

Однако вышеописанный алгоритм не является эффективным. Так если массив будет состоять из 100 элементов и искомый будет где-то в конце, то придется сделать чуть менее 100 сравнений. Если же массив будет отсортирован, то можно использовать бинарный поиск, который эффективнее.

Бинарный поиск заключается в нахождении середины массива или его отрезка и сравнении этой середины с искомым значением. Если значение оказывается больше, то далее исследуется лишь половина, где все числа больше. Эта половина в свою очередь делится на две части и ее середина сравнивается с искомым значением. Как только середина отрезка совпадет с искомым значением, поиск следует прервать. Если же совпадения не произойдет, то индексы начала и конца отрезка поиска как бы перекроют друг друга: начало станет на 1 больше, чем конец.

алг 
нач
  цел таб 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
  кц
  вывод нс
  цел начало, конец, середина, элемент
  ввод элемент
  конец := 20
  середина := div(конец,2)
  начало := 1
  нц пока arr[середина] <> элемент и начало <= конец
    если элемент > arr[середина] то
      начало := середина + 1
     иначе
      конец := середина - 1
    все
    середина := div(конец+начало,2)
  кц
  если начало > конец то
    вывод "Элемент не найден"
   иначе 
    вывод "Элемент найден на ", середина, "-м месте" 
  все
кон

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

1 4 8 12 14 17 21 23 27 29 31 35 39 41 45 46 50 54 56 58 
23
Элемент найден на 8-м месте
2 6 8 11 14 16 21 24 27 29 32 35 38 40 44 46 50 53 55 59 
43
Элемент не найден