1

Суть: есть массив элементов, и для поиска элемента в нём нужно применить троичный поиск. Однако везде в интернете имеются лишь алгоритмы для функции (причём она должна сначала возрастать, а затем убывать) и ни одного алгоритма для массива ... Как мне адаптировать алгоритм для этого случая?

11
  • Какой "троичный поиск"? Вы о чем? Че-то не понял... Чем не устраивает простой пробег по массиву и поиску нужного элемента?
    – BOPOH
    25 окт 2015 в 6:08
  • О, так здесь еще и упорядоченный массив же, а значит вместо O(N) можно применить бинарный поиск за O(log N)
    – BOPOH
    25 окт 2015 в 6:10
  • Не устраивает тем, что в условии задан именно троичный поиск. И ещё надо проверить, насколько он быстрее того же бинарного.
    – Byulent
    25 окт 2015 в 6:18
  • Тогда при чем здесь "поиск элемента", если надо искать экстремум? И массив точно упорядоченный? Если так, то что мешает применить тот же троичный поиск для поиска экстремума, задав граничные условия, чтобы не выйти за границы массива. Тогда поиск закончится именно тогда, когда начнут нарушаться эти граничные условия. Правда в этом случае непонятно что искать - максимум или минимум, т.к. есть и то, и другое. Может просто оригинальная задача немного по-другому сформулирована?
    – BOPOH
    25 окт 2015 в 6:24
  • Задача: определить, есть ли в массиве элемент или нет. Повторить 5 раз для эл-тов, которые есть, и для эл-тов, которых нет. Алгоритм поиска - троичный поиск (который препод назвал "третичным")
    – Byulent
    25 окт 2015 в 6:28

1 ответ 1

1

Есть вариант поиска, который можно назвать троичным - это когда используются варианты "меньше", "равно" и "больше" (есть такие задачи на взвешивание монет). Похожую конструкцию имел оператор IF в языке Фортран, когда за выражением следовали три метки.

Выразим идею троичного поиска с помощью несуществующей условной конструкции вида

ift (expr) ? {<} : {=} : {>}. 

Если размерность массива a меньше bb = 2n, то алгоритм для определения номера элемента в массиве может быть таким:

i=0;
for (b=bb/2; b>0; b/=2){ 
    aa = a[i+b];
    ift(x - aa) ? {} : {i+=bb; break;} : {i += b;}
}

Таким образом, троичный поиск экономит одну итерацию.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.