Using Binary Search with Vectors.
15,936
You are exiting your function on the first miss with the misplaced 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;
}
Author by
user2757849
Updated on June 04, 2022Comments
-
user2757849 almost 2 years
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.
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.
My Binary search:
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; } }
My Algo:
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; } }
}