我正在尝试实现一种算法,它对第一个 vector 中的每个字符串在第二个 vector 中进行二分搜索,如果找到匹配项,则输出“YES:”,否则输出“No:”。
现在在我的程序中,我的算法总是输出“NO:”,我无法找出出了什么问题。任何提示或提示将不胜感激。
我的二进制搜索:
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;
}
关于c++ - 对 vector 使用二分搜索。,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/18774858/