Алгоритм двоичного поиска

Алгоритм двоичного поиска предполагает на каждом шаге деления массива на две части и отбрасывание той его части, элементы которой заведомо имеют значения либо меньше, либо больше искомого. Именно это повторяющееся деление на два послужило причиной того, что данный алгоритм был назван двоичным поиском. Псевдокод алгоритма приведен ниже. Входными параметрами алгоритма являются: Value - искомое значение; Array[] - массив элементов; FirstIndex - индекс начала фрагмента массива; LastIndex - индекс конца фрагмента массива.

Общий алгоритм

function Search(Value, Array[], FirstIndex, LastIndex) {
     MiddleIndex:= FirstIndex+(LastIndex-FirstIndex +1) div 2;
     if (Value=Array[MiddleIndex]) then return MiddleIndex;
     if (Value < Array[MiddleIndex]) then {
          if (FirstIndex=MiddleIndex) then return Null;
          Index:=Search(Value, Array[],FirstIndex, MiddleIndex-1);
          if (Index <> Null) then return Index; else return Null;
     }
     if (Value > Array[MiddleIndex]) then {
          if (MiddleIndex=LastIndex) then return Null;
          Index:=Search(Value, Array[],MiddleIndex+1, LastIndex);
          if (Index <> Null) then return Index; else return Null;
     }
}