Лабораторная работа №1 Предмет: Алгоритмы и структуры данных

Ташкентский университет информационных технологий имени
Мухаммада ал-Хоразмий Каршинский филиал 
 
 
 
 
 
 
 
 
Лабораторная работа
№ 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 и т.д. 
Недостатками такого алгоритма является требование упорядоченности 
данных, а также возможности доступа к любому элементу данных за 
постоянное (не зависящее от количества данных) время. Таким образом 

алгоритм не может работать на неупорядоченных массивах и любых 
структурах данных, построенных на базе связных списков.