在C++中，查找未排序数组中元素的起始索引和结束索引

1. 简介

在C++中，对于已经排好序的数组，可以使用二分查找算法在O(log n)的时间复杂度下查找元素。但是，如果数组是未排序的，二分查找方法就不能使用了。

本文将介绍如何在未排序的数组中查找元素的起始索引和结束索引，同时提供两种实现方式，一种使用STL库函数，另一种手动实现。

2. 查找未排序数组中元素的起始索引和结束索引的算法

2.1 算法思路

算法思路为先对数组进行排序，然后使用二分查找寻找元素。一旦找到元素的位置，就继续向左和向右遍历数组，直到元素不再出现为止。

2.2 STL库函数实现

C++ STL提供了sort函数，可以将未排序的数组进行排序。同时，STL也提供了lower_bound和upper_bound函数，可以在已经排序的数组中查找元素的起始位置和结束位置。

下面是使用STL库函数实现的代码：

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
int main()
{
     vector<int> arr = { 1, 2, 3, 4, 5, 6, 6, 6, 7, 8 };
     int target = 6;
     int start = lower_bound(arr.begin(), arr.end(), target) - arr.begin();
     int end = upper_bound(arr.begin(), arr.end(), target) - arr.begin() - 1;
     if (start > end)
     {
          cout << "Element is not present in the array" << endl;
     }
     else
     {
          cout << "Element is present in the array, ";
          cout << "starting index = " << start << ", ";
          cout << "ending index = " << end << endl;
     }
     return 0;
}

该代码首先定义了一个未排序的数组arr和一个目标元素target。然后使用lower_bound函数查找元素的起始位置，使用upper_bound函数查找元素的结束位置。最后通过计算得到的位置确定元素是否在数组中存在，并打印起始位置和结束位置。

2.3 手动实现

另一种实现方式是手动遍历数组，实现算法思路中的遍历过程。下面是手动实现的代码：

#include <iostream>
#include <vector>
using namespace std;
pair<int, int> search(const vector<int>& arr, int target)
{
     int n = arr.size();
     int start = -1, end = -1;
     for (int i = 0; i < n; i++)
     {
          if (arr[i] == target)
          {
               if (start == -1)
                    start = i;
               end = i;
          }
     }
     return { start, end };
}
int main()
{
     vector<int> arr = { 1, 2, 3, 4, 5, 6, 6, 6, 7, 8 };
     int target = 6;
     auto result = search(arr, target);
     if (result.first == -1)
     {
          cout << "Element is not present in the array" << endl;
     }
     else
     {
          cout << "Element is present in the array, ";
          cout << "starting index = " << result.first << ", ";
          cout << "ending index = " << result.second << endl;
     }
     return 0;
}

该代码首先定义了一个未排序的数组arr和一个目标元素target。然后使用自定义的search函数查找元素的起始位置和结束位置。最后通过计算得到的位置确定元素是否在数组中存在，并打印起始位置和结束位置。

3. 总结

本文介绍了如何在未排序的数组中查找元素的起始索引和结束索引，同时提供了两种实现方式，一种使用STL库函数，另一种手动实现。其中，STL库函数实现简单快捷，但需要对整个数组进行排序，时间复杂度为O(nlogn)；手动实现虽然需要遍历数组，但不需要对整个数组进行排序，时间复杂度为O(n)。