10%

[crez73]

Доступа на хабр у меня нет потому напишу тут.

Задача состоит в написании алгоритма двоичного поиска:
Алгоритм двоичного поиска похож на то, как мы ищем слово в словаре. Открываем словарь посередине, смотрим в какой из половин будет нужное нам слово. Допустим, в первой. Открываем первую часть посередине, продолжаем половинить, пока не найдем нужное слово.

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

Распространенные ошибки:
- не работает с массивом из 0/1/2 элементов
- не находит первый или последний элемент
- некорректно работает, если элемента в массиве нет
- некорректно работает, если в массиве есть повторяющиеся элементы
- обращение к элементами за пределами массива
- козырная, которая была в JDK, переполнение целого при вычислении среднего индекса

Бредовая идея какая-то. Для чего нужно это написание кода на бумажку без тестирования?! Проверить умение сосредотачиваться и считать в уме?! Шли бы они тогда в цирк или шахматисты.
Да и сама суть ошибок странная, граничные условия обычно проверяются отдельно, к алгоритму это отношение имеет слабое.



function Find( pBuffer : PByteArray; intLength : Integer; btValue : Byte ) : Integer;
var
intPos : Integer;
begin
intPos := intLength div 2;

if ( intLength < 2 ) then
Result := 0
else
begin
if ( pBuffer[intPos] = btValue ) then
Result := intPos
else if ( pBuffer[intPos] > btValue ) then
Result := Find( @pBuffer[0], intPos, btValue )
else
Result := intPos + Find( @pBuffer[intPos], intLength - intPos, btValue );
end;
end;

function DoSearch( pBuffer : PByteArray; intLength : Integer; btValue : Byte ) : Integer;
var
intRes : Integer;
begin
Result := -1;

if not ( pBuffer = nil ) and ( intLength > 0 ) then
begin
intRes := Find( pBuffer, intLength, btValue );

if ( pBuffer[ intRes ] = btValue ) then
Result := intRes;
end;
end;

P.S.: Да, я пишу на Дельфи.
P.S.S.: Потратил я на это дело 15 - 45 мин. И 2-3 раза прогнал в дебагере.