Скачать: CL | DM;

Поиск элемента в массиве   Найти похожие ветки 

← →
Дас Виндовс 45   (2004-02-23 14:12) [0]

Нет ли более оптимального алгоритма для поиска некоторого элемента в массиве, чем сравнение через цикл?

---

← →
Гаврила   (2004-02-23 14:20) [1]

если массив отсортирован, то есть метод дихотомии
пример смотри в VCL коде
TStringList.IndexOf

---

← →
pasha_golub ©   (2004-02-23 14:21) [2]

Гаврила (23.02.04 14:20) [1]

Ну зачем такие матюки, сказал бы методом деления пополам :-)
Не все же консерватории заканчивали :-)

---

← →
Defunct ©   (2004-02-23 14:23) [3]

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

А алгоритм поиска выглядеть так:
1. Устанавливаем индекс начала массива на первый элемент массива, индекс конца - на последний.
2. Проверяем средний элемент между индексом начала и конца.
3. если меньше - смещаем индекс конца массива на этот элемент.
4. если больше - смещаем индекс начала массива на этот элемент.
5. Если индекс начала и индекс конца массива равны - поиск завершен, иначе повторяем искать с п.2

---

← →
Дас Виндовс 45   (2004-02-23 14:27) [4]

А можно с примерами?
Или ссылочку.
А какой из них самый эффективный?

Спасибо.

---

← →
Гаврила   (2004-02-23 14:33) [5]

>>Defunct © (23.02.04 14:23) [3]
похоже, это тоже самое, там так все и работает
>>Дас Виндовс 45 (23.02.04 14:27) [4]
Я же говорю, пример в VCL коде
>>pasha_golub © (23.02.04 14:21) [2]
уже и повыпендриваться нельзя :-)))

---

← →
Defunct ©   (2004-02-23 14:45) [6]

Самый эффективный с хеш таблицами, толко он сложноват.
Пример бинарного поиска пожалуйста:
(не забывайте, массив должен быть предварительно отсортирован)

Var A:Array[1..100] Of Integer;

Function Found(Value:Integer):Boolean;
Var MinIndex,MaxIndex : Integer;
CurrentIndex : Integer;
Begin
MinIndex := 1;
MaxIndex := 100;
Result := False;
While (Not Result) And (MinIndex<>MaxIndex) And (MinIndex<MaxIndex-1) Do
Begin
CurrentIndex := (MinIndex + MaxIndex) Div 2;
If Value = A[CurrentIndex] Then Result := True Else
If Value < A[CurrentIndex] Then MaxIndex := CurrentIndex Else
If Value > A[CurrentIndex] Then MinIndex := CurrentIndex;
End;
End;

procedure TForm1.Button1Click(Sender: TObject);
Var I:Integer;
begin
For I:=1 To 100 Do A[i] := I*2;

If Found(58) Then ShowMessage("Найден")
Else ShowMessage("Не найден");
end;

---

← →
Владислав ©   (2004-01-23 13:58) [7]

Какого размера массив? Как часто он изменяется?

---

← →
Digitman ©   (2004-02-24 15:58) [8]

> Дас Виндовс 45 (23.02.04 14:12)


приведи конкр.пример объявления/иниц-ции массива - будут и рекомендации

---

Страницы: 1 вся ветка

Скачать: CL | DM;



Память: 0.46 MB
Время: 0.009 c