将二元搜索与向量一起使用. [英] Using Binary Search with Vectors.

问题描述

我正在尝试实现一种算法，该算法针对第一个向量中的每个字符串在第二个向量中进行二进制搜索，如果找到匹配项，则输出"YES:"，否则返回"No:".

I'm trying to implement an algorithm that for each string in the first vector it does a binary search in the second vector and will output "YES:" if it finds a match or "No:" otherwise.

现在，在我的程序中，我的算法始终输出"NO:"，并且我无法找出问题所在.任何提示或技巧将不胜感激.

Right now with my program my algo always outputs "NO:" and I can't find out what's going wrong. Any hints or tips would be appreciated.

我的二进制搜索:

bool binary_search(const vector<string>& sorted_vec, string key) {
size_t mid, left = 0 ;
size_t right = sorted_vec.size(); // one position passed the right end
while (left < right) {
    mid = left + (right - left)/2;
    if (key > sorted_vec[mid]){
        left = mid+1;
   } else if (key < sorted_vec[mid]){                                        
        right = mid;
   } else {                                                                  
        return true;

            }                                                                
        return false;                                                        
    }
}

我的算法:

if(algo_speed == "fast"){

    string key = fileContent[i];

    while(getline(ifs1, line)){

            fileContent1.push_back(line);

    }

    sort(fileContent1.begin(), fileContent1.end());
    for(size_t i = 0; i < fileContent.size(); i++){
    string temp = fileContent[i];
    bool found = binary_search(fileContent1,temp) ;

     if(found == true) {
            cout << "YES:" << fileContent.at(i) << endl;
        } else {
            cout << "NO:" << fileContent.at(i) << endl;
        }
    }

}

推荐答案

由于第一个未命中的 return false :

bool binary_search(const vector<string>& sorted_vec, string key) {
   size_t mid, left = 0 ;
   size_t right = sorted_vec.size(); // one position passed the right end
   while (left < right) {
      mid = left + (right - left)/2;
      if (key > sorted_vec[mid]){
          left = mid+1;
      }
      else if (key < sorted_vec[mid]){                                        
        right = mid;
      }
      else {                                                                  
        return true;
     }                                                                                                               
   }

   return false;      
}

这篇关于将二元搜索与向量一起使用.的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！