|
|
Регистрация | << Правила форума >> | FAQ | Пользователи | Календарь | Поиск | Сообщения за сегодня | Все разделы прочитаны |
|
Опции темы | Поиск в этой теме | Опции просмотра |
|
#1
|
||||
|
||||
Поиск строки в массиве из N элементов
Собственно вопрос в названии. Дан массив из 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; Програмистами не рождаются, ими становятся! |
#2
|
||||
|
||||
Если список сортированный, то можно сделать чтобы искало логарифмически быстро.
— Как тебя понимать? — Понимать меня не обязательно. Обязательно меня любить и кормить вовремя. На Delphi, увы, больше не программирую. Рекомендуемая литература по программированию |
#3
|
||||
|
||||
Если в массиве записаны и отсортированы числа, то да.
А если там записаны слова, тут я не понимаю сути поиска, даже если отсортировать по алфавиту. M.A.D.M.A.N., Можешь показать функцию поиска? Програмистами не рождаются, ими становятся! |
#4
|
||||
|
||||
Символ строки есть число. Берешь середину массива, первую букву, если искомая больше этой, то берешь правую половину массива, повторяешь до тех пор, пока не дойдешь до искомой строки.
— Как тебя понимать? — Понимать меня не обязательно. Обязательно меня любить и кормить вовремя. На Delphi, увы, больше не программирую. Рекомендуемая литература по программированию |
#5
|
||||
|
||||
Хорошо, а если у меня много строк, которые начинаются с одинаковых букв, ибо в массиве не 1 буква записана, а слово.
Попадаю в ситуацию, с левого краю нужные буквы и с правого краю нужные буквы, я так понимаю начинаем искать по второй букве, и тут второй вопрос, - может получиться что во вновь делимой половине, окажется что слова и требуемой первой буквой находятся не с начала и не до конца, а в центре т.е. начинаю искать по второй букве и случайно она может совпать с теми которые вначале-вконце, а значит первая букава не совпадает... так много IF в этом алгоритме. Даже боюсь предположить как реализовывать Програмистами не рождаются, ими становятся! Последний раз редактировалось SCrat.ORS, 12.02.2015 в 21:57. |
#6
|
||||
|
||||
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; — Как тебя понимать? — Понимать меня не обязательно. Обязательно меня любить и кормить вовремя. На Delphi, увы, больше не программирую. Рекомендуемая литература по программированию Последний раз редактировалось M.A.D.M.A.N., 12.02.2015 в 22:47. |
#7
|
||||
|
||||
Вопрос был - "можно ли организовать поиск, не перебирая все элементы". Ответ: можно в сортированном (хотя бы по первым буквам) массиве.
Простейший вариант: Идем по массиву, ищем первую букву. Код:
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; jmp $ ; Happy End! The Cake Is A Lie. |