介绍
在本实验中,我们将学习如何使用 C++ 中的改进二分查找算法在已排序数组中找到给定数字的首次出现位置。
在本实验中,我们将学习如何使用 C++ 中的改进二分查找算法在已排序数组中找到给定数字的首次出现位置。
首先,让我们使用 touch
文本编辑器在 ~/project
目录下创建一个名为 main.cpp
的 C++ 代码文件。
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
。
在主函数中,我们将创建一个数组,调用第 3 步中创建的 first
函数并传入适当的参数,然后将结果输出到控制台。将以下代码复制并粘贴到 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++ 代码。
g++ main.cpp -o main && ./main
如果一切顺利,输出将是 The index of the first occurrence of 4 is: 3
。
在本实验中,我们学习了如何使用 C++ 中的改进二分查找算法在已排序数组中找到给定数字的首次出现位置。我们创建了一个 first()
函数来实现该算法。