Двоичный и линейный поиск в отсортированных двусвязных списках

Question

Я делаю проект колледжа по управлению библиотеками, используя двусвязные списки. В двусвязном списке хранятся идентификаторы книг во время сортировки.

Я попытался вычислить прошедшее время для наихудшего случая для линейного и двоичного поиска. Следующие результаты:

Binary search: 0.311ms
Linear search: 0.228ms
[Number of inputs(id's): 10000000]

МОЙ ВОПРОС:

Несмотря на то, что бинарный поиск требует O (logn) сравнений, прошедшее время было больше из-за того, что потребовалось O (n) обходов, пока не было найдено среднее значение. Есть ли лучший алгоритм поиска для отсортированного двусвязного списка, чем громоздкий линейный поиск?

Моя реализация для нахождения среднего значения, необходимого для бинарного поиска:

struct node* middle(node* start, node* last) 
{ 
    if (start == NULL) 
        return NULL; 
    struct node* slow = start; 
    struct node* fast = start -> next; 
    while (fast != last) 
    { 
        fast = fast -> next; 
        if (fast != last) 
        { 
            slow = slow -> next; 
            fast = fast -> next; 
        } 
    } 
    return slow; 
} 

Answer 1

прошедшее время было больше из-за того, что потребовалось O (n) обходов, пока не будет найдено среднее значение.

Когда вы вставляете новые элементы в связанный список, вы также можетеотслеживать средний элемент, как вы делаете с первым и последним.Хотя функция вставки будет более сложной.
Я бы использовал структуру для связанного списка с 4 полями:

• начальный узел
• средний узел
• последний узел
• длина

Answer 2

Двоичный поиск достигает O (log N) сложность в количестве сравнений. При использовании с массивом доступ к i-му элементу массива осуществляется в постоянное время, что не влияет на общую сложность времени.

Со списком, одиночно или двукратно связанным, доступ к i-му элементу занимает i шагов. В вашем примере доступ к среднему элементу выполняется за несколько шагов, пропорциональных длине списка. Как следствие, сложность этого поиска по-прежнему составляет O (log N) сравнений, но O (n) для выбора элементов для сравнения, что становится доминирующим фактором.

Answer 3

Ваше сравнение должно быть невероятно медленным, чтобы оправдать всю эту навигацию. Я не могу придумать лучшего способа, чем линейный поиск Если вы можете изменить структуры и CRUD, вы, безусловно, можете индексировать ключевые точки («A» начинается здесь, «B» начинается здесь и т. Д.), И это позволит вам лучше угадать начало и направление вашего линейного поиска.

Я думаю, вы обнаружите, что связанный список, двойной или другой, не является отличным выбором для случайного поиска или обновления по порядку. Используйте B-дерево, которое лучше подходит для ситуаций, которые вы указали в своем вопросе и комментариях.