Ich habe ein Array von wenigen sich wiederholenden Elementen, ich möchte den Index des sich wiederholenden Elements finden, das dem Ende des Arrays am nächsten ist

Question

Ich habe ein Array von wenigen sich wiederholenden Elementen, und ich möchte den Index des sich wiederholenden Elements finden welches dem Ende des Arrays am nächsten ist.

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

Das war einfach, aber wenn das Array sehr groß ist, nehme an, wenn Größe des Arrays 10 war^6 dann könnte es einige Zeit in Anspruch nehmen. Mir wurde gesagt, dass ein wirtschaftlicher Weg die binäre Suche ist! Wie kann ich die binäre Suche verwenden, wenn es mehrere Elemente gibt, um den Index des sich wiederholenden Elements zu finden, das dem Ende am nächsten ist, wenn man bedenkt, dass das sich wiederholende Element gegeben ist?

Answer 1

Offensichtlich ist eine binäre Suche der Weg zu gehen. Ich würde vorschlagen, auf std::upper_bound zu schauen. Auch in den Referenzen erwähnt sind Beispiele, wie eine Umsetzung aussehen kann:

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

Quelle auch cppreference.com.