Я не могу написать бинарный поиск

Недавно (буквально два года назад) тут пробегала статья Только 10% программистов способны написать двоичный поиск. Двоичный поиск — это классический алгоритм поиска. Мало того, это еще чрезвычайно простой алгоритм, который можно очень легко описать: берем отсортированный массив, смотрим в середину, если не нашли там число, в зависимости от того, что в середине — ищем это число этим же методом либо в левой части, либо в правой, откидывая средний элемент. Для функций также, просто берем не массив, а функцию. Все очень и очень просто, алгоритм описан почти везде, все баги словлены и описаны.

Так вот, я не могу реализовать двоичный поиск. Для меня он ни капельки не тривиален. Наверное, я ненастоящий программист. А ведь так и есть, я всего-лишь студент, но ведь это не оправдание? Если точнее, я не могу реализовать хороший корректный красивый двоичный поиск. Все время у меня вылезает проблема либо с корректностью, либо с красивостью, либо и с тем, и с другим. Так что, да, заголовок немного желтоват. Прежде чем читать этот топик, напишите свою версию бинарного поиска — для отсортированного массива. Причем, в зависимости от параметра, поиск должен выдавать или первый элемент, или любой из дублирующих. Еще для сравнения, напишите бинарный поиск для функций

Для начала, я буду писать код на C#. Я надеюсь, поклонники других языков с легкостью поймут мой код. Границы поиска я буду представлять в виде полуинтервала [left; right), т.е. точка left включается, а точка right выключается. Для меня полуинтервалы удобнее, к их поведению я уже привык, кроме того, использование полуинтервалов имеет некоторые преимущества при программировании различных алгоритмов (о чем мы поговорим позже). Вообще, использовать полуинтервалы более правильно с точки зрения поддержки «единого стиля программирования», так как я пишу циклы вот так:а не так: Я буду писать одновременно рекурсивную и итеративную версию, но мне ближе рекурсивная, так что не обессудьте. Для рекурсивной версии мы сделаем вот такую вот красивую обертку:

Первая попытка

Это дает хорошее понимание, что массив надо бить на интервал от [0, 3) и от [4, 7), т.е. от [left, mid) и до [mid + 1, right). Надо заметить, что существовала еще и «нулевая» версия (для статьи), в которой индексы были написаны по памяти, и, естественно, написаны они были неправильно. Самое интересное, что если я пишу алгоритм на листочке, то никаких ошибок не появляется, а если пишу на компьютере, они вылазят как грибы после дождя.

Кстати, теперь можно добавить еще одну причину к использованию полуинтервалов: если у нас есть интервал [left, right], то мы должны его разбить на [left, mid — 1] и [mid + 1; right] (что конечно, чуть проще для запоминания, но весьма странно). У полуинтервалов различие в индексах равно 1 (одному элементу, который мы выбрасываем), а у интервалов — 2 — магической цифре, взятой с потолка.

Особенно это заметно для сортировки слиянием, где для полуинтервалов различия в индексах нету (массив делится на [left, mid) и [mid, right)), а для интервалов появляется различие равное 1 (так как массив делится на [left, mid] и [mid + 1, right], или [left, mid — 1] и [mid, right]).

Теперь, осталось определить, в какой части массива нужно искать элемент, в зависимости от того, меньше ли средний элемент (array[mid]), чем ключ (key). Сделать это весьма просто — нужно просто подставить сначала один знак, проверить, работает ли программа, а если не работает, то другой :-). Почему-то именно такой способ проверки я и использую. Мне постоянно кажется, что перекомпилировать быстрее, чем «подумать».

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

Вторая попытка

Хорошо, нам надо останавливать алгоритм, когда мы не можем найти элемент в массиве. Но мы же должны что-то возвратить, верно? Или хотя-бы кинуть исключение. Что возвратить? Может быть магическое число (к примеру, -1)? Или заменить int на int? и возвратить null? (int? в c# — это число, которому можно присвоить null). Или может быть вернуть предполагаемое место в массиве, где мог-бы быть элемент, но его нет? Или все-таки кинуть исключение? Или… Это достаточно интересный вопрос, почти такой же как и «в чем смысл жизни?». Кроме интересности, эти вопросы объединяет тот факт, что ответ на оба вопроса можно сформулировать следующим образом: что хотите, то и выбирайте. Конечно, найдутся люди, которые скажут, что нужно возвращать только null, и только null.

Я предпочитаю в таком случае возвратить специальное число -(1 + left), так как, бинарный поиск может использоваться для того, чтобы вставить новый элемент, и потеря информации будет вредна. Конечно, можно написать две версии алгоритма — одна будет возвращать специальное число, а вторая кидать исключение. Хотя это и нехорошо для принципа DRY, если в вашем языке нету чего-нибудь мощного вроде макросов, которые создают функции при компиляции. Ну или можно засунуть в алгоритм параметр, обозначающий что делать.

Кстати, останавливать рекурсию мы будем в случае left == right, т.е., когда интервал стал таким — [left, right). Ну или в случае, когда right — left < 1 или right — left <= 0. Последний, кстати, полезнее, поскольку нам могли передать что-то не то в функцию (в итеративную версию, там где нету обертки).

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

Попытка №3

На всякий случай: один из вариантов проверки направления сортировки не учитывал, что массив может быть пуст. Я решил не выделять этот фейл в отдельную попытку.

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

Что плохого в этом коде, помимо того что он ужасен и комментарии написаны на непонятном языке? Этот код позволяет задуматься, а почему нельзя было написать 3 варианта поиска, а не городить малопонятного монстрика? Нет, если присмотреться, он вполне неплох, хотя и плох (если сравнить с другими версиями выше).

Кстати, я сейчас подумал, что гораздо красивее представлять интервалы в виде объектов с волшебными свойствами/методами getFirstHalf, getSecondHalf (получают первую и вторую половину интервала), getStartPoint/getLastPoint (получают первую/последнюю точку интервала), increaseLength/decreaseLength (меняют длину интервала), moveStartPoint. Ну или еще какими-нибудь другими волшебными свойствами. Это чрезвычайно упростило бы понимание двоичного поиска, да и вообще любых алгоритмов.

Для того, чтобы написать алгоритм, нам нужно будет использовать числа с плавающей точкой. Плавающая точка… Если вы еще не произносите рефлекторно мат, когда слышите словосочетание «плавающая точка», значит вы плохо с ней работали. Давайте посмотрим код:

Задайте себе несколько вопросов. Этот код работает? Почему он работает? Что за прикол с абсолютным сравнением float'ов? (если у вас не вызывает этот момент удивления, прошу читать статью Что нужно знать про арифметику с плавающей запятой?, возможно, найдете что-нибудь полезное). Хотите еще один клевый вопрос? Каков тип интервала left; right? Это [left, right], или [left, right), или (left, right], или (left, right)? Внимательно подумайте. Запустите этот кусок кода и подумайте еще раз:

Итак, точка left у нас включается и исключается в зависимости от погоды на Марсе. Для точки right погода на Марсе тоже имеет важное значение (проверено). Т.е. мы складываем два числа a и b, делим сумму на два и получаем либо a, либо b, либо что-то между ними. Это забавно. На самом деле, эта фишка скорее всего прописана в стандарте, а может, вычисление mid зависит от опций компилятора/платформы. А может действительно от погоды на Марсе.

Чтобы соблюсти хоть какой-то контракт, нам нужно в обертку поместить проверки func(left) == key и func(right) == key, тогда наши интервалы всегда будут закрытыми с обоих сторон.

В качестве задачки, кому скучно будет: попытайтесь скрестить поиск по массиву с поиском по функции, покажите своего монстра. Те, кому не настолько скучно, могут показать хотя-бы альтернативные примеры реализаций бин. поиска, более красивые или с чуть-другими идеями. Те, кому очень-очень скучно, я предлагаю такую задачку: напишите бинарный поиск по функции, если все числа — рациональные, и представляются в виде несократимой дроби a/b. В качестве очень жестокого издевательства: числа a и b безграничные. Супер-сложность: все еще за O(lgn).

Вообще, хочется спросить: а что все-таки лучше — одна монструозная функция, которая поддерживает выбор первого/последнего/любого из них или три функции, чрезвычайно похожих, но немного не таких?