[Q] Быстpый поиск в отсоpтиpованном списке

From

Stanislav Shwartsman (2:400/520)

To

Oleg Shatalov

Date

2002-09-18T23:55:29Z

Area

RU.ALGORITHMS

Hello Oleg!

18 Sep 02 23:47, you wrote to Andrey Belyakov:

 >> Хммм... Осталось выяснить, как ты собираешься получить L[size/2]
 >> в _списке_, пусть даже двунаправленном и отсортированном...  :)

 OS> Дело в том, что списки можно представить как динамический массив и
 OS> доступ к каждому элементу происходит по его индексу без каких-либо
 OS> дополнительных затрат времени.

 OS> При этом, такая организация выгоднее бинарного дерева за счет того,
 OS> что не нужно хранить ссылки на дочерние ветви, т.е. получается
 OS> экономия памяти. Единственный минус - при вставке элемента в такой
 OS> массив приходится перемещат все элементы, стоящие после него.

 И тогда это будет уже не список, а динамический массив ...
 Если уж на то пошло, то лучше список в виде дерева представить :)

    E-mail: gate@fidonet.org.il
    Voice Phones: 972-4-8330554 (home), 972-5-4481073 (cell)

Bye !
Stanislav     (AKA Night's Man)                        [Team Technion]
---
 * Origin: Gate From Another World ... From Haifa, Israel (2:400/520)