私はいくつかの反復要素の配列を持っています、私は配列の最後に最も近い反復要素のインデックスを見つけたいと思います

Question

私はいくつかの反復要素の配列を持っています、そして、これは配列の最後に最も近いものです。

#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; 
} 

これは簡単でしたが、配列が非常に大きい場合は、配列のサイズが10^6だったとしたら、時間がかかります。私はバイナリ検索を使うことを経済的な方法で伝えました！反復要素が与えられていることを考慮して、最後に最も近い反復要素のインデックスを見つける複数の要素がある場合、バイナリ検索を使用するにはどうすればよいですか？

Answer 1

明らかにバイナリ検索が行われます。私は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; 
} 

ソースもcppreference.comです。