Что может быть быстрее бинарного поиска? Другой бинарный поиск.

function Search4b(Val: integer; const Arr: IntegerArray; Right: integer): integer;
var
  Left: integer;
begin;
  Result:=Right shr 1;
  Left:=0;
  if Right>=0 then while true do begin;
    if Val>Arr[Result] then begin;
      Left:=Result+1;
      Result:=(Left + Right) shr 1;
      if Left<=Right then continue else break;
      end
    else if Val<Arr[Result] then begin;
      Right:=Result+(-1);
      Result:=(Left + Right) shr 1;
      if Left<=Right then continue else break;
      end
    else exit;
    end;
  Result:=-1;
  end;

Особенности этого шедевра человеческой мысли:

1. Левая и правая граница поиска включают первый и последний элементы массива, которые могут содержать искомое значение. Кто-то думал, что может быть иначе?
2. Как обычно, наш двоичный поиск содержит три ветки – так алгоритм выглядит проще. Второй переход все равно не предсказывается и на скорость практически не влияет.
3. Мы даже не пытаемся предварительно считать сравниваемый элемент из массива во временную переменную – пусть это сделает компилятор, если сможет.
4. При вычислении новой правой границы используется сложение, а не вычитание, чтобы лишний раз намекнуть компилятору на возможность использования инструкции LEA.
5. Индекс среднего элемента округляется, как принято, влево – в данном случае так проще и быстрее.
6. Вычисление очередного индекса среднего элемента начинается как можно раньше, еще до проверки окончания цикла.
7. Проверка окончания цикла выполняется отдельно для левой и правой ветки, чтобы уменьшить количество переходов.

на главную