[SCrat.ORS]

Собственно вопрос в названии. Дан массив из n элементов:

Код:

var
mas: array of string;

Нужно найти номер элемента массива в котором содержится искомая строка.
Реально ли организовать поиск не перебирая все элементы?

Код:

function Find(const AText: string; const AValues: array of string): Integer;
var
  I: Integer;
begin
  Result := -1;
  for I := Low(AValues) to High(AValues) do
    if AText=AValues[i] then
    begin
      Result := I;
      Break;
    end;
end;

Есть ли способ быстрее?

[M.A.D.M.A.N.]

Если список сортированный, то можно сделать чтобы искало логарифмически быстро.

[SCrat.ORS]

Если в массиве записаны и отсортированы числа, то да.
А если там записаны слова, тут я не понимаю сути поиска, даже если отсортировать по алфавиту.
M.A.D.M.A.N., Можешь показать функцию поиска?

[M.A.D.M.A.N.]

Символ строки есть число. Берешь середину массива, первую букву, если искомая больше этой, то берешь правую половину массива, повторяешь до тех пор, пока не дойдешь до искомой строки.

[SCrat.ORS]

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

[M.A.D.M.A.N.]

http://www.swissdelphicenter.ch/torr...de.php?id=1916

Код:

function BinSearch(Strings: TStringArray; SubStr: string): Integer;
var
  First: Integer;
  Last: Integer;
  Pivot: Integer;
  Found: Boolean;
begin
  First  := Low(Strings); //Sets the first item of the range
  Last   := High(Strings); //Sets the last item of the range
  Found  := False; //Initializes the Found flag (Not found yet)
  Result := -1; //Initializes the Result

  //If First > Last then the searched item doesn't exist
  //If the item is found the loop will stop
  while (First <= Last) and (not Found) do
  begin
    //Gets the middle of the selected range
    Pivot := (First + Last) div 2;
    //Compares the String in the middle with the searched one
    if Strings[Pivot] = SubStr then
    begin
      Found  := True;
      Result := Pivot;
    end
    //If the Item in the middle has a bigger value than
    //the searched item, then select the first half
    else if Strings[Pivot] > SubStr then
      Last := Pivot - 1
        //else select the second half
    else 
      First := Pivot + 1;
  end;
end;

[Bargest]

Вопрос был - "можно ли организовать поиск, не перебирая все элементы". Ответ: можно в сортированном (хотя бы по первым буквам) массиве.
Простейший вариант:
Идем по массиву, ищем первую букву.

Код:

i := 0;
while i < length(arr) do
begin
   if arr[i][0] > s[0] then
   begin
     i := length(arr);
     break;
   end;
   if arr[i][0] = s[0] then
     break;
   i := i + 1;
end;
if i >= length(arr) then exit; // нет строки

Либо дошли до конца, либо нашли индекс первой строки, в которой совпадает первая буква.
Далее ищем саму строку, пока первые символы совпадают:

Код:

while i < length(arr) do
begin
   if arr[i][0] > s[0] then
   begin
     i := length(arr);
     break;
   end;
   if arr[i] = s then
   begin
     foundIndex := i;
     break;
   end;
   i := i + 1;
end;

Теперь foundIndex содержит номер строки.

[icWasya]

Ну посмотрите реализацию TStringList.
Или сразу используйте именно его.

[SCrat.ORS]

Результаты тестирования.

Массив 1 700 слов, 10000 циклов поиска первой, средней, последней строки.
1. Тупо перебор по всем строкам: 0,0073 мсек.
2. Бинарный поиск: 0,0656 мсек.
3. (Не знаю как назвать): 0,0036 мсек.
4. TStringList.IndexOf: 0,2713 мсек.

Массив 170 000 слов, 1000 циклов поиска первой, средней, последней строки.
1. Тупо перебор по всем строкам: 1,119 мсек.
2. Бинарный поиск: 11,93 мсек. !!!!
3. (Не знаю как назвать): 1,114 мсек.
4. TStringList.IndexOf: 27,81 мсек.

Массив 1 700 000 слов, 100 циклов поиска первой, средней, последней строки.
1. Тупо перебор по всем строкам: 12,55 мсек.
2. Бинарный поиск: Error (Stack Overflow)
3. (Не знаю как назвать): 11,71 мсек.
4. TStringList.IndexOf: 275,88 мсек.

Время указано среднее на 1 поиск.

Значит получается что эффективнее всего использовать тупо перебор всех строк, так как он по времени не на много отстает от лидера, но его преимущество в том, что массив не нужно сортировать, а соответственно не затрачивается время на сортировку.

[M.A.D.M.A.N.]

Значит так и делай.

[icWasya]

А StringList в Ваших тестах - сортированный?

[madMonia]

Какие-то странные у вас результаты. Бинарный поиск - это то, что предложил M.A.D.M.A.N, и он должен значительно быстрее работать, чем простой перебор. И уж точно не должен возвращать Stack Overflow. А что за алгоритм "не знаю как назвать".

[SCrat.ORS]

Массив используется сортированный, а значит и StringList тоже.
Результаты показаны по функциям представленных в постах, без изменений алгоритма.
(Не знаю как назвать) - это алгоритм предложенный Bargest

[lmikle]

Поищи еще реализацию HashMap'а.

[Bargest]

Значит получается что эффективнее всего использовать тупо перебор всех строк

Просто на всякий случай, использовались не те же самые строки, что лежали в массиве? Я к тому, что не получилось ли так, что в тесте строка находилась по совпадению указателя на строку, а не самой строки?