К. Поляков, 2010 -2012 Программирование на алгоритмическом языке. Часть II Тема 3. Двоичный поиск. - презентация

1 К. Поляков, Программирование на алгоритмическом языке. Часть II Тема 3. Двоичный поиск

2 Программирование на алгоритмическом языке. Часть II К. Поляков, Поиск в массиве 2 Задача – найти в массиве элемент, равный X, или установить, что его нет. Решение: для произвольного массива: линейный поиск (перебор) недостаток: низкая скорость Как ускорить? – заранее подготовить массив для поиска как именно подготовить? как использовать «подготовленный массив»?

3 Программирование на алгоритмическом языке. Часть II К. Поляков, Линейный поиск 3 i:= 1 нц пока A[i] X i:= i + 1 кц если i

4 Программирование на алгоритмическом языке. Часть II К. Поляков, Двоичный поиск X = 7X = 7 X < 8X < X > 4X > X > 6 1.Выбрать средний элемент A[c] и сравнить с X. 2.Если X = A[c], нашли (выход). 3.Если X < A[c], искать дальше в первой половине. 4.Если X > A[c], искать дальше во второй половине.

= L c:= div(R+L, 2); если X < A[c] " title="Программирование на алгоритмическом языке. Часть II К. Поляков, 2010-2012 http://kpolyakov.narod.ru Двоичный поиск 5 L:= 1; R:= N; nX:= 0 если nX > 0 то вывод "A[", nX, "]=", X иначе вывод "Не нашли" все нц пока R >= L c:= div(R+L, 2); если X < A[c] " class="link_thumb"> 5 Программирование на алгоритмическом языке. Часть II К. Поляков, Двоичный поиск 5 L:= 1; R:= N; nX:= 0 если nX > 0 то вывод "A[", nX, "]=", X иначе вывод "Не нашли" все нц пока R >= L c:= div(R+L, 2); если X < A[c] то R:= c – 1 все если X > A[c] то L:= c + 1 все кц номер среднего элемента если X = A[c] то nX:= c; выход все если X = A[c] то nX:= c; выход все нашли Почему нельзя нц пока R > L … кц ? ? выйти из цикла сдвигаем границы 1LcRN = L c:= div(R+L, 2); если X < A[c] "> = L c:= div(R+L, 2); если X < A[c] то R:= c – 1 все если X > A[c] то L:= c + 1 все кц номер среднего элемента если X = A[c] то nX:= c; выход все если X = A[c] то nX:= c; выход все нашли Почему нельзя нц пока R > L … кц ? ? выйти из цикла сдвигаем границы 1LcRN"> = L c:= div(R+L, 2); если X < A[c] " title="Программирование на алгоритмическом языке. Часть II К. Поляков, 2010-2012 http://kpolyakov.narod.ru Двоичный поиск 5 L:= 1; R:= N; nX:= 0 если nX > 0 то вывод "A[", nX, "]=", X иначе вывод "Не нашли" все нц пока R >= L c:= div(R+L, 2); если X < A[c] ">

6 Программирование на алгоритмическом языке. Часть II К. Поляков, Сравнение методов поиска 6 ЛинейныйДвоичный подготовканетотсортировать число шагов N = 2N = 222 N = N = N = N N log 2 N + 1

7 Программирование на алгоритмическом языке. Часть II К. Поляков, Задания 7 «3»: Написать программу, которая сортирует массив по возрастанию и ищет в нем элемент, равный X (это число вводится с клавиатуры). Использовать двоичный поиск. «4»: Написать программу, которая сортирует массив ПО УБЫВАНИЮ и ищет в нем элемент, равный X (это число вводится с клавиатуры). Использовать двоичный поиск. «5»: Написать программу, которая считает среднее число шагов в двоичном поиске для массива из 32 элементов в интервале [0,100]. Для поиска использовать 1000 случайных чисел в этом же интервале.