Как мога да намеря границите на подмножество от подреден списък? - алгоритъм, търсене

Имам следната дилема: Имам списък с низове и искам да намеря набор от низове, който започва с определен префикс. Списъкът е сортиран, така че наивното решение е следното:

Извършете двоично търсене на префиксите на комплекта и когато намерите елемент, който започва с префикса, преместете линейно, докато не достигнете горната част на подгрупата.

Това обаче се случва в линейно време и се чудех дали някой може да предложи по-ефективен начин да го направи.

Отговори:

Направете двоично търсене на върха и направете двоичентърсете дъното. Щом намерите първия хит, знаете, че горната част е над тази точка, а долната част е по-долу (или в този момент и в двата случая). След като имате горната и долната част, имате решение.

Можете да направите подобно двоично търсене в началотоелемент, с изключение на това, че низът, който трябва да търсите, е първият низ, който започва с префикс строго по-голям от въпросния префикс. Това също така отнема O (lg n) време.

След като намерите един елемент в комплекта, просто запазете двоичното търсене, докато не намерите крайните точки.