Ташкентский университет информационных технологий имени
Мухаммада ал-Хоразмий Каршинский филиал
Лабораторная работа № 1
Предмет: Алгоритмы и структуры данных
Задача: Используя метод последовательного и двоичного поиска, найдите элемент и количество сравнений из массива A
Выполнил: Саттаров Зафаржон Кахорович (ТТ-12-20 S)
Задача: Используя метод последовательного и двоичного поиска, найдите элемент и количество сравнений из массива A
Предположим, что массив из 12-ти элементов отсортирован по возрастанию:
Пользователь задает искомое значение (ключ поиска). Допустим 4. На первой итерации массив делится на две части (ищем средний элемент – midd): (0 + 11) / 2 = 5 (0.5 отбрасываются). Сначала, проверяется значение среднего элемента массива. Если оно совпадает с ключом – алгоритм прекратит работу и программа выведет сообщение, что значение найдено. В нашем случае, ключ не совпадает со значением среднего элемента.
Если ключ меньше значения среднего элемента, алгоритм не будет проводить поиск в той половине массива, которая содержит значения больше ключа (т.е. от среднего элемента до конца массива). Правая граница поиска сместится (midd – 1). Далее снова деление массива на 2.
Ключ снова не равен среднему элементу. Он больше него. Теперь левая граница поиска сместится (midd + 1).
На третьей итерации средний элемент – это ячейка с индексом 3: (3 + 4) / 2 = 3. Он равен ключу. Алгоритм завершает работу.
Пример:
Результат:
Двоичный поиск является эффективным алгоритмом — его оценка сложности O(log2(n)), в то время как у обычного последовательного поиска O(n). Это значит, что например, для массива из 1024 элементов линейный поиск в худшем случае (когда искомого элемента нет в массиве) обработает все 1024 элемента, но бинарным поиском достаточно обработать log2(1024) = 10 элементов. Такой результат достигается за счет того, что после первого шага цикла область поиска сужается до 512 элементов, после второго – до 256 и т.д.
Недостатками такого алгоритма является требование упорядоченности данных, а также возможности доступа к любому элементу данных за постоянное (не зависящее от количества данных) время. Таким образом алгоритм не может работать на неупорядоченных массивах и любых структурах данных, построенных на базе связных списков.
Достарыңызбен бөлісу: |
