查找元素的第一个和最后一个出现

题：

给定一个数组，该数组按升序排序并带有重复的元素，并给出键。查找该密钥的第一个和最后一次出现。

例：

数组= {2，3，4，4，4，5，6，7，8};
键= 4。

这里“4”重复3次。我们需要发送开始和结束事件“4”

解：

此问题可以通过二进制搜索解决。

我们需要编写2个函数，一个函数找到数字的第一个出现，另一个函数找到数字的最后一个出现。

那么如何找到数字的第一次出现呢？

我们可以借助修改后的二进制搜索来实现。在这里，一旦发现任何事件，就不会从函数返回。但是我们通过将索引保存在结果变量中来对其进行修改，并使用mid更新end变量–1并搜索元素。

对于查找最后一个索引，我们也是如此。在这里，我们将中索引+ 1更新为开始索引，以找到该变量的最后一次出现。

C ++解决方案

#include <iostream>
using namespace std;

int find_first_occurrence(int arr[], int length, int key)
{
    int start = 0;
    int end = length - 1;

    int result = -1;

    while (start <= end)
    {
        int mid = (start + end)/2;

        // if key is found, ignore right part
        if (key == arr[mid])
        {
            result = mid;
            end = mid - 1;
        }

        // if key is less than the mid element, ignore right half
        else if (key < arr[mid])
            end = mid - 1;

        // if target is more than the mid element, ignore left half
        else
            start = mid + 1;
    }

    // return the first occurrence index or -1 if the element is not found
    return result;
}

int find_last_occurrence(int arr[], int length, int key)
{
    int start = 0;
    int end = length - 1;

    int result = -1;

    while (start <= end)
    {
        int mid = (start + end)/2;

        // if key is found, ignore right part
        if (key == arr[mid])
        {
            result = mid;
            start = mid + 1;
        }

        // if key is less than the mid element, ignore right half
        else if (key < arr[mid])
            end = mid - 1;

        // if target is more than the mid element, ignore left half
        else
            start = mid + 1;
    }

    // return the first occurrence index or -1 if the element is not found
    return result;
}
  

int main(void) 
{ 
    int arr[] = {1, 2, 3, 4, 4, 4, 4, 5, 6, 7 }; 
    int key = 4; 
    int size = sizeof(arr) / sizeof(arr[0]); 

    int first_occurance = find_first_occurrence(arr, size, key);

    int last_occurance = find_last_occurrence(arr, size, key);

    cout<<"The first occurrence is " <<first_occurance<<" and the last occurrence is "<<last_occurance<<endl;

    return 0; 
} 

输出：

The first occurrence is 3 and the last occurrence is 6