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

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

← →
Piero   (2005-11-30 12:55) [0]

Подскажите алгоритм поиска элемента в массиве,
массив очень большой (>10000 элементов), я так помню, что алгоритм дерева, дает наилучшие результаты. Спасибо

---

← →
Глупые Вопросы ©   (2005-11-30 14:08) [1]

Все алгоритмы поиска, насколько я понимаю, делаются в отсортированном массиве. В принципе можешь сделать и сортировку деревом, здесь тебе поможет, например, книга Вирта "Алгоритмы + структуры данных=программы".
Но это большой гемор. Проще в уже отсортированном массиве использовать дихотомический поиск (массив делится пополам, смотриться в какой из половин массива находится требуемое значение и так далее поеа не найдём).
Вообще, наверное есть уже готовые структуры, которые всё вышеописанное делают, как например STL в Visual C++

---

← →
MBo ©   (2005-11-30 14:08) [2]

Для нахождения лучшего решения в конкретном случае - читать книжки по алгоритмам.

Общий случай - массив отсортировать, и использовать бинарный поиск.

---

← →
Piero   (2005-11-30 14:26) [3]

Массив отсортирован, а вот насчет бинарного поиска это верно, если есть готовый напишите

---

← →
Piero   (2005-11-30 14:30) [4]

просто его написать нужно аккуратно, если нет такого элемента, то найти, те элементы между кот и должно находиться искомое значение, если есть готовое, напишите

---

← →
Anatoly Podgoretsky ©   (2005-11-30 14:32) [5]

Piero   (30.11.05 12:55)  я так помню, что алгоритм дерева, дает наилучшие результаты.

Неправильно понимаешь, дерево может быть вырожденым, тогда время поиска равно N
Двоичный поиск в дает время Log N

---

← →
Piero   (2005-11-30 14:36) [6]

ладно, не надо, ничего писать я уже придумал

---

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

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



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