Trouble with Binary Search

Question

there. I am trying to have a binary search of a text file. I am comparing text file one to text file two. However, My binary algorith seems to not work nd print out the element it has found. My text file 2 is a sorted list and my textfile1 is the key. I need some guidance on how to figure this problem out. Here is my code:

bool binary_search(const vector<string>& sorted_vec, const vector<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;
 for(int i=0;i<sorted_vec.size();i++){
 if (key[i] > sorted_vec[mid]){ //
 left = mid+1;
 }else if (key[i] < sorted_vec[mid]){
 right = mid;
 }else{
 return true;
 }
 }
 return false;
 }
}

• user425495: That's because your key is changing on every iteration of your for loop. Modify your binary_search implementation to take a single key, and wrap a for-loop around it for your vector of keys.
• user529758: std::binary_search...

Answer 1

The search key is changing on every iteration of the for loop in your binary_search implementation. Modify your implementation to take a single key, and wrap a for-loop around it for your vector of keys. However I agree with @H2CO3 that you should be using std::binary_search:

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
vector<int> sorted_vec = {1, 2, 3, 4, 5, 6, 7, 8};
vector<int> keys = {3, 5, 19, 27, 0, 2};
int main() {
 for(const auto &key : keys) {
 cout << binary_search(sorted_vec.cbegin(), sorted_vec.cend(), key) << endl; 
 }
}

Output

1
1
0
0
0
1

If you wish to use your own binary_search, then you'll need to fix your current implementation.