我有一些重复元素的数组，我想找到最接近数组末尾的重复元素的索引

I have an array of few repetitive elements, and I want to find the index of the repetitive element which is closest to end of the array.

我有一些重复元素的数组,我想找到最接近数组末尾的重复元素的索引。

#include<iostream>
uisng namespace std;
int main()
{
  int arr[15]={1,2,3,4,5,6,7,8,8,8,9,10,11,12,13};   // 8 is repeating 3 times

// lets find the index of element 8 which is closest from the end

 int index;

for(int i=0;i<15;i++)
  {
    if(arr[i]==8)
     {
       index=i;break;
     }
  }      
      cout<<index;
return 0;
}

This was easy but if the array is very large, suppose if size of array was 10^6 then it could take up some time. I have been told one economic way is to use binary search! How can I use the binary search if there are multiple elements to find index of the repetitive element which is closest to the end, considering the repetitive element is given?

这很容易,但如果数组非常大,假设如果数组大小为10 ^ 6则可能需要一些时间。我被告知一种经济方式是使用二分搜索!如果有多个元素可以找到最接近末尾的重复元素的索引,那么如何使用二进制搜索,考虑到给出了重复元素?

1 个解决方案

#1

Clearly a binary search is the way to go. I would propose to look at std::upper_bound. Also mentioned in the references are examples how an implementation may look like:

显然,二元搜索是可行的方法。我建议看一下std :: upper_bound。参考文献中还提到了实现可能如下所示的示例:

template<class ForwardIt, class T>
ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value)
{
    ForwardIt it;
    typename std::iterator_traits<ForwardIt>::difference_type count, step;
    count = std::distance(first,last);

    while (count > 0) {
        it = first; 
        step = count / 2; 
        std::advance(it, step);
        if (!(value < *it)) {
            first = ++it;
            count -= step + 1;
        } else count = step;
    }
    return first;
}

Source also cppreference.com.

来源也是cppreference.com。

#1