Simple binary search

Question

Here the task (in Indonesian).

I think my binary search algorithm is correct.

Ideone

 #include<bits/stdc++.h>
using namespace std;
vector<pair<string, string>> v;
int awal1 = 1;
string check(string s, int awal, int akhir){
    int tengah = (awal+akhir)/2;
    bool temukan = false;
    if(v[tengah].first == s){
        return v[tengah].second;
        temukan = true;
    }
    else if(v[tengah].first > s){
        return check(s, awal, tengah-1);
    }
    else if(v[tengah].first < s){
        return check(s, tengah+1, akhir);
    }
    if(temukan == false) return "NIHIL";
} 

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
     string s, s1, s2; vector<string> h; 
    int n, p;
    cin >> n >> p;
    for(int i=1;i<=n;i++){
        cin >> s >> s1;
        v.push_back(make_pair(s, s1));
    }
    for(int j=1;j<=p;j++){
        cin >> s2;
        h.push_back(s2);
    }
    for(int i=1;i<=h.size();i++){
        cout << check(h[i], 1, v.size()) << "\n";   
    }
    /*for(int i=0;i<v.size();i++){
        cout << v[i].first << " " << v[i].second << "\n";
    } */
}

Answer 1

This is a non standard header.

#include<bits/stdc++.h>

The "bits" directory is an implementation detail of your compiler. You should NEVER use it in your code.

Your headers should be:

#include <vector>
#include <iostream>

You should not do this:

using namespace std;

Read the details about the issues here: Why is “using namespace std” considered bad practice?

You should avoid using global variables.

vector<pair<string, string>> v;

Here you are locking your check() function to searching only one list. It should search any list for the key.

This global variable does not seem to be used anywhere:

int awal1 = 1;

Bounds checking:

string check(string s, int awal, int akhir){

If awal and akhir are equal there is nothing to check. You have gone beyond the range. So You need to do a test here. If these two are equal then you failed to find the data.

Note: That akhir is one beyond the end of the range you are checking. For the very right hand end of the vector this means beyond the end of the v which means that accessing it is undefined behavior and likely to cause a crash.

This value is always false.

    bool temukan = false;

Because this statement is never executed.

    if(v[tengah].first == s){
        return v[tengah].second;

        // The line above is a return. 
        // So the next line is never reached.
        // So we never execute this.
        temukan = true;
    }


    // So in this line  `temukan` is always false.
    // So this `if` test is always true
    // So this would always return 'NIHIL'
    if(temukan == false) return "NIHIL";

BUT. In the same function you also have another set of if else statements. That always result in a return. So the code never falls through to the last 'NIHL' statement.

if(v[tengah].first == s){              // Equal
    return v[tengah].second;
}
else if(v[tengah].first > s){          // Greater
    return check(s, awal, tengah-1);
}
else if(v[tengah].first < s){          // Less
    return check(s, tengah+1, akhir);
}

One of those branches must be true (unless you were comparing floats). So the code will never go past these set of tests.

So there are some massive bugs in the function check(). You definitely need to fix these. I am not going to fix them because I think it would do you good to try and work out what the correct solution is. But as it stands this would fail any unit tests you should have written.

This is C code.

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

What you probably want is the C++ std::fstream class.

One variable per line please:

     string s, s1, s2; vector<string> h; 
    int n, p;

As containers like arrays/vectors are 0 based. We usually loop from 0 to 1 less than the number.

    for(int i=1;i<=n;i++){

    // Most C/C++/Java/C# etc programmer would write that loop as:
    for(int i = 0; i < n; ++i) {

Yes this works.

        v.push_back(make_pair(s, s1));

But you can use the emplace_back() method which makes it easier to read and removes an unneeded copy.

        v.emplace_back(s, s1);

As I mentioned above containers are indexed from 0.

        cout << check(h[i], 1, v.size()) << "\n";   

So passing a 1 here is wrong. As you will never find the first element. You should have noticed there was not check for "agung". You can't find this person if you search from 1 as they are in position 0. Unfortunately your check loop also started at 1 so your code missed it.

Answer 2

You have implemented the midpoint calculation like this:

int tengah = (awal+akhir)/2;

Which to be fair is super common and it is the most obvious way to do. But it has a problem: for a long enough vector, awal + akhir can overflow. That is undefined behaviour in C++, and it is also actually bad in practice. The most likely consequence is that awal + akhir results in a (very large) negative number, subsequently dividing it by 2 still results in a negative number that is only slightly less big. Indexing into the vector with a negative index will very likely crash.

Here are some ways to avoid that:

int tengah = ((unsigned)awal + akhir) / 2;

The unsigned average of two non-negative signed numbers neither overflows nor wraps. Converting the result back to signed is always safe.

int tengah = awal + (akhir - awal) / 2;

Subtracting a smaller non-negative number from a bigger non-negative number is always safe. Adding half of it to the lower number is also safe because the average must be somewhere "between" the inputs so it cannot go out of range.