如何使用二進制搜索將元素插入到已排序的向量中

你好我有一個問題，我不知道我的實現是否使用二進制搜索插入到向量中是正確的。我有兩個向量一個存儲類對象。第二個是假設要排序的那個。第二個向量保存第一個向量的索引，這些索引假設按照字典順序排序（從小到大）。我試圖讓我的程序運行O（log（n））。這是我有...如何使用二進制搜索將元素插入到已排序的向量中

void Trendtracker:: add_hashtag(string ht) 
{ 

    Entry tweet; 
    tweet.count = 0; 
    tweet.hashtag = ht; 
    if (E.empty()) 
    { 
     E.push_back(tweet); 
     S.push_back(0); 
    } 


    int l, m, r; 
    l = 0; 
    r = S.size() -1; 

    while (l < r) 
    { 
     m =(l+r)/2; 
     if(E[S[m]].hashtag == ht)//found #1 
      return; 
     else if (E[S[m]].hashtag < ht)// searches right 
      l = m +1; 
     else 
      r = m-1; // searches left 

    } 

    if(l ==r && E[S[l]].hashtag == tweet.hashtag)// found #2 
     return; 

    E.push_back(tweet); 

    //if not found and lower than the lowest 
    if(l==0 && ht < E[S[l]].hashtag) 
    { 
     //S[0]= E.size()-1; 
     S.insert(S.begin(), E.size()-1); 
    } 

    // if not found but is higher than highest 
    else if(l == S.size()-1 && E[S[l]].hashtag < ht) 
    { 
     S.push_back(E.size()-1); 
    } 

    // if new hashtag goes in the second index 
    else if(l==0&& r==0 && E[S[r]].hashtag< ht) 
    { 

     S.insert(S.begin()+1, E.size()-1); 
    } 

    // if not found and l & r are somewhere in the middle 
    else 
    { 

     S.insert(S.begin()+l, E.size()-1); 
    } 
}

來源

2017-09-23 Omar

使用類似'的std :: LOWER_BOUND（）'，而不是滾動您自己：http://en.cppreference.com/w/cpp/algorithm/lower_bound –

如果'如果（E .empty（））'條件爲真，那麼你可以在執行該'if'塊後返回。執行其餘代碼沒有意義。 – MKR

如果您使用的容器在中間插入/刪除頻繁那麼std::vector可能不是你最好的選擇。

想一想：std::vector將元素存儲在連續的內存中，所以每次要插入它的中間時，都會移動它後面的所有元素。查找速度更快（如果排序的話更多），但插入時的開銷是可以考慮的。

您可以查看實現鏈表的列表或其他類型的容器，因爲插入操作與創建節點一樣簡單，在元素之前和元素本身以及元素之後更改next和prev指針。

希望它可以幫助

來源

2017-09-23 08:07:17 jjimenezg93

如何使用二進制搜索將元素插入到已排序的向量中

回答

相關問題