x 的第一次和最后一次出现

Question

问题链接如下：
https://www.geeksforgeeks.org/problems/first-and-last-occurrences-of-x3116/1

给定一个包含 n 个元素且可能有重复元素的排序数组 arr，任务是找到给定数组中元素 x 的第一次和最后一次出现。
注意：如果在数组中找不到数字 x，则将两个索引都返回为 -1。

示例1：

输入：
n=9，x=5

arr[] = { 1, 3, 5, 5, 5, 5, 67, 123, 125 }

输出：
2 5

说明：
5 第一次出现在索引 2 处，最后一次出现 5 位于索引 5 处。

示例2：

输入：
n=9，x=7

arr[] = { 1, 3, 5, 5, 5, 5, 7, 123, 125 }

输出：
6 6

说明：
7 的第一次和最后一次出现位于索引 6 处。

您的任务：

因为，这是一个功能问题。您不需要进行任何输入，因为它已经由驱动程序代码完成。您只需要完成函数 find()，该函数以数组 arr、整数 n 和整数 x 作为参数并返回所需的答案。

预期时间复杂度：O(logN)
预期辅助空间：O(1).

限制：
1≤N≤106
1 ≤ arr[i],x ≤ 109

这是我的代码：

class solution
{
    public:
    vector<int> find(int arr[], int n , int x )
    {
        //first occurence -------------------------------
        int s=0;
        int e=n-1;
        int target=x;
        int first=-1;
        
        while(s<=e){
            int mid=(s+e)/2;
            if(arr[mid]==target){
                first=mid;
                e=mid-1;
            }
            if(arr[mid]<target){
                // R.S
                s=mid+1;
            }
            else{
                // l.S
                e=mid-1;
            }
        }
    
        // last occurence ----------------------------------
        
        s=0;
        e=n-1;
        target=x;
        int last=-1;
        
        while(s<=e){
            int mid=(s+e)/2;
            if(arr[mid]==target){
                last=mid;
                s=mid+1;
            }
            if(arr[mid]<target){
                // R.S
                s=mid+1;
            }
            else{
                // l.S
                e=mid-1;
            }
        }
        //return -----------------------------------------------
        return{first,last};

    }
};

编译结果：

Compilation Completed

For Input:
9 5
1 3 5 5 5 5 67 123 125

Your Output:
2 4

Expected Output:
2 5

任何人都可以解决这个问题并给出正确的描述吗？并解释一下我的代码有什么问题？

Answer 1

在两个 while 循环中都有一个拼写错误。例如，让我们考虑第一个 while 循环

while(s<=e){
    int mid=(s+e)/2;
    if(arr[mid]==target){
        first=mid;
        e=mid-1;
    }
    if(arr[mid]<target){
    ^^^^^^^^^^^^^^^^^^^^^      
        // R.S
        s=mid+1;
    }
    else{
        // l.S
        e=mid-1;
    }
}

例如，您必须将第二个 if 语句括在第一个 if 语句的 else 部分中

while(s<=e){
    int mid=(s+e)/2;
    if(arr[mid]==target){
        first=mid;
        e=mid-1;
    }
    else if(arr[mid]<target){
    ^^^^^^^^^^
        // R.S
        s=mid+1;
    }
    else{
        // l.S
        e=mid-1;
    }
}

注意，这样声明函数会更好

static std::pair<ptrdiff_t, ptrdiff_t> find( const int a[], size_t n, int x )

即该函数应声明为静态成员函数。它的第一个参数应具有限定符 const。指定数组大小的第二个参数应具有 size_t 类型。如果类型为

std::pait<ptrdiff_t, ptrdiff_t>

，最好返回一个对象，而不是返回向量。

在函数定义中，您可以使用标准算法

std::equal_range

。

这是一个演示程序。

#include <iostream>
#include <utility>
#include <iterator>
#include <algorithm>

class solution
{
public:
    static std::pair<ptrdiff_t, ptrdiff_t> find( const int a[], size_t n, int x )
    {
        auto p = std::equal_range( a, a + n, x );

        if (p.first == p.second)
        {
            return { -1, -1 };
        }
        else
        {
            return { std::distance( a, p.first ), std::distance( a, p.second ) - 1 };
        }
    }
};

int main()
{
    int a[] = { 1, 3, 5, 5, 5, 5, 7, 123, 125 };

    int value = 5;

    auto result = solution::find( a, std::size( a ), value );

    if (result.first != -1)
    {
        std::cout << "The value " << value 
            << " is present in the range of indices "
            << "[ " << result.first << ", " << result.second << " ]\n";
    }
    else
    {
        std::cout << "The value " << value
            << " is not present in the array.\n";
    }

    value = 7;

    result = solution::find( a, std::size( a ), value );

    if (result.first != -1)
    {
        std::cout << "The value " << value
            << " is present in the range of indices "
            << "[ " << result.first << ", " << result.second << " ]\n";
    }
    else
    {
        std::cout << "The value " << value
            << " is not present in the array.\n";
    }
}

程序输出为

The value 5 is present in the range of indices [ 2, 5 ]
The value 7 is present in the range of indices [ 6, 6 ]