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

При решении задачи на Leetcode https://leetcode.com/problems/find-median-from-data-stream Я столкнулся с подходом сортировки вставками. Однако во всплывающем опросе упоминается использование линейного поиска вместо бинарного поиска. Интересно, почему это так, и каковы компромиссы?


binary-search insertion-sort
person Sagar Bonde    schedule 15.05.2020    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Я предполагаю, что если вы ищете номер i, вместо поиска с самого начала вы можете начать поиск с индекса i. Но это хорошо работает только в том случае, если числа не содержат много дубликатов.

person Alex Liu    schedule 17.10.2020

arrow_upward
0
arrow_downward

Задача будет стоить O(n) как при линейном поиске, так и при бинарном поиске, поэтому просто выполните более простой линейный поиск.

person Jessepinkman56    schedule 22.05.2021