Оптимальный поиск в массиве Опции

[kosyak]

Доброе всем время суток. Следующая задача: есть упорядоченный массив (например [1,6,7,9] ) и есть число N. Необходимо узнать первый элемент, который больше N. т.е. если N = 3, то первый элемент, больше N - 6. Какой алгоритм будет оптимальней для решения этой задачи?

[Client]

в отсортированном массиве по-моему проще всего искать "быстрым поиском" (или как он называется, где выбирается каждый раз только половина диапазона)

[Client]

если массив небольшой, то можно перебором, пока не найдешь нужный элемент

[Lapp]

если массив небольшой, то можно перебором, пока не найдешь нужный элемент

Client, а что значит в данном случае "небольшой"?

P.S. Способ с делением пополам называется дихотомия.

[kosyak]

Ок, спасиба. Я тоже склонялся к бинарному поиску

[Client]

это относительно я не знаю, есть ли ограничения на время выполнения или что другое. Массив из 100-200 элементов вполне можно и последовательно обработать

[Lapp]

это относительно я не знаю, есть ли ограничения на время выполнения или что другое. Массив из 100-200 элементов вполне можно и последовательно обработать

Относительно, но в меру. "Дважды два" - тоже относительно?
Если автор спрашивает про алгоритм - я думаю, из этого уже следует, что его заботит время (а может, и место). Максимальное количество итераций в дихотомии есть Log₂n, а в простом поиске равно n. Средние величины будем считать вдвое меньшими (хоть это и не совсем верно). И если отношение времен на одну итерацию при дихотомии и последовательном поиске равно k (один дихотомический шаг в k раз дольше последовательного), то для значения n, при котором дихотомия становится более выгодной, имеем уравнение:
n = k*Log₂n
Разумным значением для k представляется примерно от 4 до 8 (зависит от способов адресации, типов сравниваемых величин..) Решить это уравнение можно простым перебором. Например, при k=8 получаем:

n=16
левая часть: 16
правая часть: 32

n=32
левая часть: 32
правая часть: 40

n=64
левая часть: 64
правая часть: 48

Легко видеть, что решением является примерно n=50 (при желании можно уточнить). Вот тебе и ответ на этот вопрос )). Но:

а. нужно помнить, что он получен для k=8, в конкретных случаях нужно использовать конкретные значения k;
б. если важно место, то есть объем кода (что бывает довольно редко), то посик оптимума усложнится.

И, наконец, если все важно только время, то можно реализовать оба алгоритма и переключаться между ними в зависимости от текущего значения n (если оно не постоянно).

[kosyak]

Спасибо большое, я все понял))