Алгоритмические языки_ Лабораторная работа №3 -... Методические указания к лабораторной работе 3 по дисциплине Алгоритмические языки и программирование для студентов специальности 230100 (ивт)

• Название: Методические указания к лабораторной работе 3 по дисциплине Алгоритмические языки и программирование для студентов специальности 230100 (ивт)
• Дата: 26.08.2021
• Размер: 329 Kb.
• Имя файла: Алгоритмические языки_ Лабораторная работа №3 -...doc
• Тип: Методические указания; #228015
• страница: 4 из 6

Двоичный поиск в массиве

Если у нас есть массив, содержащий упорядоченную последовательность данных, то очень эффективен двоичный поиск.

Переменные lowerBound и upperBound содержат, соответственно, левую и правую границы отрезка массива, где находится нужный нам элемент. Мы начинаем всегда с исследования среднего элемента отрезка. Если искомое значение меньше среднего элемента, мы переходим к поиску в верхней половине отрезка, где все элементы меньше только что проверенного. Другими словами, значением upperBound становится (M – 1) и на следующей итерации мы работаем с половиной массива. Таким образом, в результате каждой проверки мы вдвое сужаем область поиска. Так, в нашем примере, после первой итерации область поиска – всего лишь три элемента, после второй остается всего лишь один элемент. Таким образом, если длина массива равна 6, нам достаточно трех итераций, чтобы найти нужное число.

Двоичный поиск - очень мощный метод. Если, например, длина массива равна 1023, после первого сравнения область сужается до 511 элементов, а после второй - до 255. Легко посчитать, что для поиска в массиве из 1023 элементов достаточно 10 сравнений.

Алгоритм двоичного поиска приведен ниже:

lowerBound = 0

upperBound = size
Повторять бесконечно

M = (lowerBound + upperBound) / 2
Если K < A[M], то

upperBound = M – 1

Иначе Если K > A[M], то

lowerBound = M + 1

Иначе

Сообщить «Элемент найден, его индекс: », M

Выход из цикла

Все если
Если lowerBound > upperBound, то

Сообщить «Элемент не найден»

Выход из цикла

Все если

Все повторять
В описанном выше алгоритме приняты следующие условия:

1. 
   size – размер массива
   
2. 
   K – число, которое нужно найти
   
3. 
   М – индекс найденного элемента.
   

7. Варианты индивидуальных заданий

	Задание	Сложность	Алгоритм сортировки	Алгоритм поиска
	элементы, присутствующие в обоих массивах А и В	1	Пузырьком	Линейный
	элементы, которые есть только в массиве А или только в массиве В	1	Пузырьком	Линейный
	элементы, которые присутствуют в массиве А, но отсутствуют в массиве В	1	Пузырьком	Линейный
	элементы, которые присутствуют в обоих массивах А и В в нескольких экземплярах	1	Пузырьком	Линейный
	элементы, которые присутствуют в нескольких экземплярах в массиве А, но отсутствуют в массиве В	1	Пузырьком	Линейный
	элементы, которые присутствуют в нескольких экземплярах либо только в массиве A, либо только в массиве В	1	Пузырьком	Линейный
	элементы, которые присутствуют в нескольких экземплярах либо в массиве А, либо в массиве В (либо в обоих массивах)	1	Пузырьком	Линейный
	элементы массива А, повторяющиеся в массиве В несколько раз	1	Пузырьком	Линейный
	элементы присутствующие в обоих массивах А и В в одном экземпляре	1	Пузырьком	Линейный
	элементы, присутствующие в одном экземпляре либо только в массиве А, либо только в массиве В	1	Пузырьком	Линейный
	повторяющиеся элементы массива А, которые есть в массиве В	1	Пузырьком	Линейный
	повторяющиеся элементы массива В, которые есть в массиве А только в одном экземпляре	1	Пузырьком	Линейный
	неповторяющиеся элементы массива А, которые присутствуют в массиве В в нескольких экземплярах	1	Пузырьком	Линейный
	элементы массива А в одном экземпляре, которые присутствуют в массиве В в нескольких экземплярах	1	Пузырьком	Линейный
	повторяющиеся элементы массива А, которых нет в массиве В	1	Пузырьком	Линейный
	элементы, присутствующие в обоих массивах А и В	2	Выбором	Линейный
	элементы, которые есть только в массиве А или только в массиве В	2	Выбором	Линейный
	элементы, которые присутствуют в массиве А, но отсутствуют в массиве В	2	Выбором	Линейный
	элементы, которые присутствуют в обоих массивах А и В в нескольких экземплярах	2	Выбором	Линейный
	элементы, которые присутствуют в нескольких экземплярах в массиве А, но отсутствуют в массиве В	2	Выбором	Линейный
	элементы, которые присутствуют в нескольких экземплярах либо только в массиве A, либо только в массиве В	2	Выбором	Линейный
	элементы, которые присутствуют в нескольких экземплярах либо в массиве А, либо в массиве В (либо в обоих массивах)	2	Выбором	Линейный
	элементы массива А, повторяющиеся в массиве В несколько раз	2	Выбором	Линейный
	элементы присутствующие в обоих массивах А и В в одном экземпляре	2	Выбором	Линейный
	элементы, присутствующие в одном экземпляре либо только в массиве А, либо только в массиве В	2	Выбором	Линейный
	повторяющиеся элементы массива А, которые есть в массиве В	2	Выбором	Линейный
	повторяющиеся элементы массива В, которые есть в массиве А только в одном экземпляре	2	Выбором	Линейный
	неповторяющиеся элементы массива А, которые присутствуют в массиве В в нескольких экземплярах	2	Выбором	Линейный
	элементы массива А в одном экземпляре, которые присутствуют в массиве В в нескольких экземплярах	2	Выбором	Линейный
	повторяющиеся элементы массива А, которых нет в массиве В	2	Выбором	Линейный
	элементы, присутствующие в обоих массивах А и В	3	Вставками	Линейный
	элементы, которые есть только в массиве А или только в массиве В	3	Вставками	Линейный
	элементы, которые присутствуют в массиве А, но отсутствуют в массиве В	3	Вставками	Линейный
	элементы, которые присутствуют в обоих массивах А и В в нескольких экземплярах	3	Вставками	Линейный
	элементы, которые присутствуют в нескольких экземплярах в массиве А, но отсутствуют в массиве В	3	Вставками	Линейный
	элементы, которые присутствуют в нескольких экземплярах либо только в массиве A, либо только в массиве В	3	Вставками	Линейный
	элементы, которые присутствуют в нескольких экземплярах либо в массиве А, либо в массиве В (либо в обоих массивах)	3	Вставками	Линейный
	элементы массива А, повторяющиеся в массиве В несколько раз	3	Вставками	Линейный
	элементы присутствующие в обоих массивах А и В в одном экземпляре	3	Вставками	Линейный
	элементы, присутствующие в одном экземпляре либо только в массиве А, либо только в массиве В	3	Вставками	Линейный
	повторяющиеся элементы массива А, которые есть в массиве В	3	Вставками	Линейный
	повторяющиеся элементы массива В, которые есть в массиве А только в одном экземпляре	3	Вставками	Линейный
	неповторяющиеся элементы массива А, которые присутствуют в массиве В в нескольких экземплярах	3	Вставками	Линейный
	элементы массива А в одном экземпляре, которые присутствуют в массиве В в нескольких экземплярах	3	Вставками	Линейный
	повторяющиеся элементы массива А, которых нет в массиве В	3	Вставками	Линейный
	элементы, присутствующие в обоих массивах А и В	4	Подсчетом	Линейный
	элементы, которые есть только в массиве А или только в массиве В	4	Подсчетом	Линейный
	элементы, которые присутствуют в массиве А, но отсутствуют в массиве В	4	Подсчетом	Линейный
	элементы, которые присутствуют в обоих массивах А и В в нескольких экземплярах	4	Подсчетом	Линейный
	элементы, которые присутствуют в нескольких экземплярах в массиве А, но отсутствуют в массиве В	4	Подсчетом	Линейный
	элементы, которые присутствуют в нескольких экземплярах либо только в массиве A, либо только в массиве В	4	Подсчетом	Линейный
	элементы, которые присутствуют в нескольких экземплярах либо в массиве А, либо в массиве В (либо в обоих массивах)	4	Подсчетом	Линейный
	элементы массива А, повторяющиеся в массиве В несколько раз	4	Подсчетом	Линейный
	элементы присутствующие в обоих массивах А и В в одном экземпляре	4	Подсчетом	Линейный
	элементы, присутствующие в одном экземпляре либо только в массиве А, либо только в массиве В	4	Подсчетом	Линейный
	повторяющиеся элементы массива А, которые есть в массиве В	4	Подсчетом	Линейный