Поиск в отсортированной последовательности

[Sarumjan]

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

[Sibedir]

ИСПРАВЛЕНО

Пусть дан массив чисел A отсортированный по возрастанию. Найти номер элемента равного X

PredPred = -1;
Pred = -1;
Cur = -1;
Len = Длина (А);
Если Len = 0 тогода ВЫХОД;
Step = Len div 2;
Cur = Pred + Step;

Пока A[Cur] <> X
|  Step = Round (Step / 2);
|  PredPred = Pred
|  Pred = Cur
|  Если A[Cur] > X то Cur = Pred - Step;
|  иначе Cur = Pred + Step;
|  Если (Cur = PredPred) или (Cur < 0) или (Cur >= Len) то
|  |  Cur = -1;
|  |  Выход из цикла
|  конец условия
конец цикла

Результат = Cur

Добавлено --------------------------------------------------------------
В Delphi есть одна проблема. Round округляет X.5 до ближайшего кратного. Т.е. Round(0.5) = 0. Как от этого избавиться не помню, поэтому:

if Step = 0 then Step := 1;

[Serge_Bliznykov]

Сообщение от Sarumjan

При этом не использовать обычный перебор и метод дихотомии(деление на пополам).

Sibedir, а разве вот это:

Step = Round (Step / 2);

не метод деления пополам?


p.s. как решать задачу я не знаю...

[Sibedir]

Тьфу ты ну ты. А я прочитал: При этом не использовать обычный перебор, а метод дихотомии(деление на пополам).
Вот балда

Добавлено --------------------------------------------------------------
Бред, конечно, но можно и так:

var
  Len: Integer;
  IndexArr: array of Integer;

procedure TForm1.FormCreate(Sender: TObject);
var
  i: Integer;
begin
  Len := StrToInt (ListBox1.Items[ListBox1.Items.Count-1]);
  SetLength (IndexArr, Len+1);
  for i := 0 to Len do IndexArr[i] := -1;
  for i := 0 to ListBox1.Items.Count-1 do IndexArr[StrToInt (ListBox1.Items[i])] := i;
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  X, R: Integer;
begin
  X := StrToInt (Edit1.Text);

  if (X < 0) or (X > Len) then
    R := -1
  else
    R := IndexArr[X];

  Edit2.Text := IntToStr (R);
end;

А если

var
  Max: Integer;
  IndexArr: array of Integer;

procedure TForm1.FormCreate(Sender: TObject);
var
  i, j: Integer;
begin
  Max := -1;
  for i := 0 to ListBox1.Items.Count-1 do begin
    j := StrToInt (ListBox1.Items[i]);
    if j > Max then Max := j;
  end;
  SetLength (IndexArr, Max+1);
  for i := 0 to Max do IndexArr[i] := -1;
  for i := 0 to ListBox1.Items.Count-1 do IndexArr[StrToInt (ListBox1.Items[i])] := i;
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  X, R: Integer;
begin
  X := StrToInt (Edit1.Text);

  if (X < 0) or (X > Max) then
    R := -1
  else
    R := IndexArr[X];

  Edit2.Text := IntToStr (R);
end;

то это еще и для несортированного массива. Но если в массив длинной 1000 затясалось число 1000000000, то это сложно назвать эффективным алгоритмом.