Введение
В этом лабе мы узнаем, как найти первое вхождение заданного числа в отсортированном массиве с использованием модифицированного двоичного поиска на C++.
Файл кода на C++
Во - первых, создадим файл кода на C++ с именем main.cpp в директории ~/project с использованием текстового редактора touch.
touch ~/project/main.cpp
Включите необходимые заголовочные файлы в код
В нашем программе необходимо включить необходимые заголовочные файлы на C++. Скопируйте и вставьте следующий код в файл main.cpp.
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
Создайте функцию для поиска первого вхождения элемента
Мы создадим функцию под названием first(), которая принимает массив, его нижний индекс, верхний индекс и элемент, который нужно найти, в качестве входных данных. Функция вернет индекс первого вхождения элемента. Включите следующий код в файл main.cpp.
int first(int a[], int l, int h, int b)
{
int res = -1;
while (l <= h)
{
int m = (l + h) / 2;
if (a[m] == b)
{
res = m;
h = m - 1;
}
else if (a[m] > b)
{
h = m - 1;
}
else
{
l = m + 1;
}
}
return res;
}
Здесь мы использовали двоичный поиск для нахождения первого вхождения элемента. Мы инициализировали переменную res значением -1, чтобы обработать случай, когда элемент отсутствует в массиве. Если средний элемент равен элементу, который мы ищем, мы храним индекс среднего элемента в res и обновляем верхний индекс до m-1, так как мы ищем первое вхождение элемента. Если средний элемент больше элемента, который мы ищем, мы обновляем верхний индекс до m-1, а если он меньше элемента, мы обновляем нижний индекс до m+1.
Реализуйте главную функцию
В главной функции мы создадим массив, вызовем функцию first, созданную на шаге 3, с соответствующими аргументами и выведем результат в консоль. Скопируйте и вставьте следующий код в функцию main.
int main()
{
int a[] = {2, 3, 3, 4, 4, 4, 4, 4, 5};
int n = sizeof(a) / sizeof(a[0]);
int k = 4; //элемент, для которого нужно найти индекс первого вхождения
int f = first(a, 0, n - 1, k);
if(f==-1)
{
cout << "Element not found\n";
}
else
{
cout << "The index of the first occurrence of " << k << " is: " << f << endl;
}
return 0;
}
Здесь мы объявили массив целых чисел под названием a и инициализировали его отсортированными значениями целых чисел. Мы также вычислили количество элементов в массиве с использованием оператора sizeof. Затем мы вызвали функцию first() с соответствующими аргументами и вывели результат.
Компилируйте и запускайте код на C++
Теперь мы можем скомпилировать и запустить код на C++ с использованием следующих команд.
g++ main.cpp -o main &&./main
Если все прошло успешно, вывод будет The index of the first occurrence of 4 is: 3.
Резюме
В этом практическом занятии мы научились искать первое вхождение заданного числа в отсортированном массиве с использованием модифицированного двоичного поиска на C++. Мы создали функцию first(), чтобы реализовать алгоритм.
