我有一個重複元素的數組，我想找到最接近數組末尾的重複元素的索引

我有一個少數重複元素的數組，我想找到重複元素的索引這最接近數組的末尾。我有一個重複元素的數組，我想找到最接近數組末尾的重複元素的索引

#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次方那麼它可能需要一些時間。我被告知一種經濟的方法是使用二進制搜索！如果有多個元素來查找最接近結束的重複元素的索引，考慮重複元素，我該如何使用二分法搜索？

來源

2017-05-23 deltaaaa

您是否嘗試編寫二分查找？想想你將如何決定遞歸和遞歸權利。 – Barry

重複元素是連續的嗎？任何其他限制，你沒有提到？ – rici

是否對數組進行排序？當你說'找到最接近數組末尾的重複元素的索引' - 是否意味着如果有多個重複元素 - 你必須找到數組中最後一個元素？ – arunk2

很明顯，二分查找是一種方法。我會建議看看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。

來源

2017-05-23 21:14:03 gue

我有一個重複元素的數組，我想找到最接近數組末尾的重複元素的索引

回答

相關問題