Задача 1 — Бинарный поиск

[ Обновление: Данный пост более не актуален, см. тему Беседы о программировании 001 :: Бинарный поиск ]

Первая беседа будет посвящена бинарному поиску. Я расскажу о некоторых неочевидных для меня в прошлом соображениях по части данного алгоритма.

Предполагается, что идея алгоритма уже хорошо ясна зрителям и поэтому изложение будет рассчитано на тех, кто может правильно его запрограммировать. Прежде чем видео будет записано, я бы хотел дать задание. Кто хочет поучаствовать, может выслать мне на почту zealint@zealcomputing.ru алгоритм бинарного поиска для решения следующей задачи.

Задан упорядоченный по неубыванию массив из N элементов (целых чисел), N — неотрицательное целое, умещающееся в 32 бита без знака. Нумерация элементов массива – от 0 до N-1. Задано число K. Отыскать в массиве ПЕРВОЕ число, НЕ МЕНЬШЕЕ, чем K. Вывести номер позиции (от 0 до N-1) найденного числа. Если такого числа в массиве нет, вывести в качестве ответа значение N. Для простоты можно считать, что элементы массива и число K также умещаются в 32 бита без знака.

Срок выполнения небольшой, чтобы не тянуть: до 15 декабря 2015 года (включительно), затем я начну готовить лекцию.

Задание можно выполнить на любом удобном для Вас языке программирования (даже на псевдоязыке), я не буду запускать код, а лишь посмотрю на логику решения. Это задание нужно лично мне, чтобы собрать определённую статистику и, возможно, собрать более полный набор ошибок при реализации бинарного поиска. Чтобы Вам же потом об этих ошибках и рассказать. Разумеется, я прошу написать свой собственный код, а не показать, как Вы вызываете функцию из стандартной библиотеки : )

Бинарный поиск – коварный алгоритм, не смотря на кажущуюся простоту, в нём полно подводных камней. Вот об этом, в частности, тоже пойдёт речь.