C++!! Левый и правый двоичный поиск. У вас есть два списка чисел, и числа в первом списке упорядочены по возрастанию
C++!! Левый и правый двоичный поиск. У вас есть два списка чисел, и числа в первом списке упорядочены по возрастанию. Вам нужно определить, для каждого числа из второго списка, какие позиции занимают первое и последнее вхождение этого числа в первом списке. Вы можете использовать встроенные функции для решения этой задачи. Исходные данные: В первой строке ввода записаны два числа N и M (1≤N,M≤20000). Во второй строке записаны N упорядоченных по возрастанию целых чисел - элементы первого списка. В третьей строке записаны M целых неотрицательных чисел - элементы второго списка. Все числа в списках являются 32-битными целыми числами со знаком. Результат: Ваша задача состоит только в переформулировке текста.
21.12.2023 03:26
Написать свой ответ:
Пояснение:
Левый и правый двоичный поиск - это алгоритмы, используемые для нахождения первого и последнего вхождения определенного элемента в упорядоченном списке чисел. Основная идея заключается в том, чтобы разделить список пополам и проверить, в какой половине может находиться искомый элемент. Если он больше или равен серединному элементу, то мы исключаем левую половину списка, иначе - правую. Затем мы повторяем этот процесс в выбранной половине, уменьшая количество элементов вдвое на каждой итерации. Когда мы находим элемент, мы запоминаем его позицию и продолжаем поиск, чтобы найти последнее вхождение.
Доп. материал:
Исходные данные:
N = 6, M = 4
Первый список: 2, 4, 5, 5, 7, 8
Второй список: 5, 8, 2, 7
Процесс левого и правого двоичного поиска:
Для числа 5: Левый индекс - 2, Правый индекс - 3
Для числа 8: Левый индекс - 5, Правый индекс - 5
Для числа 2: Левый индекс - 1, Правый индекс - 1
Для числа 7: Левый индекс - 4, Правый индекс - 4
Совет:
Для понимания работы левого и правого двоичного поиска полезно представить упорядоченный список чисел в виде таблицы или последовательности. Не забывайте, что элементы списка должны быть упорядочены по возрастанию, чтобы алгоритмы работали правильно.
Задача для проверки:
У вас есть упорядоченный список из 10 чисел: 1, 2, 3, 4, 5, 5, 7, 8, 8, 9. Найдите левый и правый индекс для числа 5.