在已排序数组中定位首次出现的位置

C++C++Beginner
立即练习

💡 本教程由 AI 辅助翻译自英文原版。如需查看原文,您可以 切换至英文原版

介绍

在本实验中,我们将学习如何使用 C++ 中的改进二分查找算法在已排序数组中找到给定数字的首次出现位置。


Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL cpp(("`C++`")) -.-> cpp/BasicsGroup(["`Basics`"]) cpp(("`C++`")) -.-> cpp/ControlFlowGroup(["`Control Flow`"]) cpp(("`C++`")) -.-> cpp/IOandFileHandlingGroup(["`I/O and File Handling`"]) cpp(("`C++`")) -.-> cpp/SyntaxandStyleGroup(["`Syntax and Style`"]) cpp/BasicsGroup -.-> cpp/arrays("`Arrays`") cpp/BasicsGroup -.-> cpp/strings("`Strings`") cpp/ControlFlowGroup -.-> cpp/conditions("`Conditions`") cpp/ControlFlowGroup -.-> cpp/while_loop("`While Loop`") cpp/IOandFileHandlingGroup -.-> cpp/output("`Output`") cpp/IOandFileHandlingGroup -.-> cpp/files("`Files`") cpp/SyntaxandStyleGroup -.-> cpp/code_formatting("`Code Formatting`") subgraph Lab Skills cpp/arrays -.-> lab-96132{{"`在已排序数组中定位首次出现的位置`"}} cpp/strings -.-> lab-96132{{"`在已排序数组中定位首次出现的位置`"}} cpp/conditions -.-> lab-96132{{"`在已排序数组中定位首次出现的位置`"}} cpp/while_loop -.-> lab-96132{{"`在已排序数组中定位首次出现的位置`"}} cpp/output -.-> lab-96132{{"`在已排序数组中定位首次出现的位置`"}} cpp/files -.-> lab-96132{{"`在已排序数组中定位首次出现的位置`"}} cpp/code_formatting -.-> lab-96132{{"`在已排序数组中定位首次出现的位置`"}} end

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++ 代码

现在,我们可以使用以下命令编译并运行 C++ 代码。

g++ main.cpp -o main && ./main

如果一切顺利,输出将是 The index of the first occurrence of 4 is: 3

总结

在本实验中,我们学习了如何使用 C++ 中的改进二分查找算法在已排序数组中找到给定数字的首次出现位置。我们创建了一个 first() 函数来实现该算法。

您可能感兴趣的其他 C++ 教程