Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/5: Рейтинг темы: голосов - 5, средняя оценка - 5.00
ninja_cat
0 / 0 / 0
Регистрация: 08.10.2012
Сообщений: 14
1

Поиск элемента в отсортированном массиве

21.02.2014, 02:53. Просмотров 849. Ответов 5
Метки нет (Все метки)

какое минимальное колличество итераций при поиске элемента в отсортированом массиве по возрастанию из 100 элементов?
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.02.2014, 02:53
Ответы с готовыми решениями:

Оптимальный поиск элемента в массиве
Столкнулся с проблемой поиска оптимального алгоритма нахождения индекса нужного мне элемента в...

Поиск максимального элемента в двумерном массиве
Здравствуйте! Собственно вопрос - оптимальный алгоритм. Есть ли тут вообще алгоритм который находит...

Двоичный поиск в массиве ВСЕХ вхождений искомого элемента
У Вики есть такой чудесный код: def check(x, m): return x < m def binSearch(lst, x): #...

Поиск максимального элемента в массиве методом "разделяй и властвуй"
Я в недоумении, поиск максимального элемента в массиве сводится к цикличной проверке всех его...

Поиск элемента в не отсортированном массиве
Здравствуйте. Необходимо написать программу, которая генерирует массив с помощью RND, а затем найти...

5
Mysterious Light
Эксперт по математике/физике
4079 / 1993 / 404
Регистрация: 19.07.2009
Сообщений: 3,009
Записей в блоге: 21
21.02.2014, 03:47 2
Поставьте правильно вопрос.

Я отвечу: одна.
Например, у нас алгоритм подряд перебирает все элементы, сравнивая с образцом:
Javascript
1
2
for(var i=0; i<100; ++i);
    if(a[i] == x) return i;
если a=[1,2,3,4,5,...,100] и x=1, то, очевидно, программа сделает одну итерацию и выдаст результат.

Вы возразите: у меня фиксируются массив и элемент, а что если они произвольны? А Вы об этом же ни слова не сказали!
Допустим, Ваш вопрос о наименшем по всем вариантам массива и элемента числе итераций.

Тогда мой ответ: одна итерация.
Javascript
1
2
3
4
5
6
7
8
for(;;) {
    if(a[0] == x) return 0;
    if(a[1] == x) return 1;
    if(a[2] == x) return 2;
    if(a[3] == x) return 3;
    ...
    if(a[99] == x) return 99;
}
В этом цикле больше одной итерации в принципе не может быть. Если присмотреться, здесь даже сам цикл избыточный, можно убрать его без ущерба программе. Но по факту, только одна итерация будет совершена.

На самом деле, два ответа совсем не используют факт отсортированности массива. Первый ответ базируется на том, что для любого алгоритма поиска существует такие a и x, что первая же итерация завершит работу цикла. Второй ответ базируется на том, что длина списка нам заведомо известна, поэтому можно любой любой алгоритм поиска переписать в виде ветвлящегося поиска только из if-else без циклов вообще.
1
ninja_cat
0 / 0 / 0
Регистрация: 08.10.2012
Сообщений: 14
21.02.2014, 03:54  [ТС] 3
Mysterious Light, под количеством итераций имеется число сравнений, которое будет произведено.
0
Mysterious Light
Эксперт по математике/физике
4079 / 1993 / 404
Регистрация: 19.07.2009
Сообщений: 3,009
Записей в блоге: 21
21.02.2014, 04:37 4
Бинарный поиск сработает не более, чем за 7 итераций. Уменшить верхнюю границу не получится.
1
ninja_cat
0 / 0 / 0
Регистрация: 08.10.2012
Сообщений: 14
21.02.2014, 04:39  [ТС] 5
Mysterious Light, а как Вы это посчитали, расскажите пожалуйста.
0
Mysterious Light
Эксперт по математике/физике
4079 / 1993 / 404
Регистрация: 19.07.2009
Сообщений: 3,009
Записей в блоге: 21
21.02.2014, 04:55 6
Лучший ответ Сообщение было отмечено ninja_cat как решение

Решение

1. Сравниваем с 49 элементом, определяем половину [0..49] или [50..99]. Длина диапазона 50.
2. Сравниваем с 24 или 74 и определяем четверть [0..24], [24..49], [50..74], [74..99]. Длина диапазона 25.
3. Сравниваем с 12, 37, 62 или 86 и определяем диапазон [0..13], .... Длина диапазона 12 или 13.
4. Сравниваем с центральным элементом диапазона, длина новой половины 6 или 7.
5. Сравниваем с центральным элементом диапазона, длина новой половины 3 или 4.
6. Сравниваем с центральным элементом диапазона, длина новой половины 1 или 2.
7. Определяем нужный элемент.
Менее, чем за 7 сравнений, найти элемент нельзя. Можно показать, что, если бы существовал такой алгоритм, то для него можно было б найти два элемента в массиве, для которых алгоритм вернул бы одно и то же число, что невозможно. Это следует напрямую из того, что каждый элемент в массиве однозначно кодируется набором ответов, которые даёт сравнение на каждой итерации. Если бы итераций было не больше 6 в самом худшем случае, то каждому элементу были бы сопоставлены цепочки из не более чем 6 булевых величин, всего таких цепочек не более 64, поэтому по меншей мере два элемента в массиве будут кодироваться одной и той же цепочкой, а значит, дадут одинаковый результат на таком гипотетическом алгоритме, что противоречиво.

Замечу, что если можно за одно сравнение определить, является ли одно число больше, меньше или равным другому числу (т.е. не булевое сравнение, а троичное), то число итераций в худшем случае ограничивается 6.
1
21.02.2014, 04:55
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.02.2014, 04:55

Поиск нужного элемента в отсортированном массиве
Здраствуйте. Решаю задачу 2 день, неполучается. Подумал сюда обратиться. В общем задача такая. Есть...

Поиск индекса заданного элемента в отсортированном массиве
1. Заполнить статический массив значениями 90, 76, 54, 23, 56, 12, 48. Результат в виде таблицы...

Поиск элемента в отсортированном массиве методом бинарного дерева
Как найти элемент в отсортированном массиве, методом бинарного дерева, не могу найти этот...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru