UOJ Passport Checking : Binary Search Method

The Interpol database contains a list of N stolen passport numbers. We have another list of M passport numbers to check if they are stolen or not.

Input

  • The first line of the input contains an integer N.
  • The next N lines contains the list of N stolen passport numbers, one passport number per line.
  • The next line of the input contains an integer M.
  • The next M lines contains the list of M passport numbers, one passport number per line.

Output

Output the total number of stolen passports in the list of M passports.

Constraints

  • Time Limit: 3s
  • Memory Limit: 64MB
  • 1≤N≤100,000
  • 1≤M≤100,000
  • Passport numbers are alphanumeric (combination of alphabetic and numeric characters) and are of length at most 15

Problem Source: UTP Online Judge

If we solve this problem with linear search, we will end up with TLE (Time Limit Exceeded). So, one way to solve this is by Binary Search that we discussed previously. One problem is, we have to sort our data before we perform Binary Search, what we have to do is include code:

#include <algorithm>

sort(stolen, stolen + N);

After we have the sorting algorithm as the intermediate step, we can now construct our code:

C++

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;
 
int main() {
    int N, M;
    string stolen[100000];
 
    cin >> N;
    for(int i=0;i<N;i++) {
        cin >> stolen[i];
    }
 
    sort(stolen,stolen+N);
 
    int cnt, hi, lo = 0;
    string target;
 
    cin >> M;
    for (int i=0; i<M; i++){
        cin >> target;
 
        lo = 0;
        hi = N - 1;
 
        int mid;
        while (lo<=hi){
            mid = (lo+hi)/2;
            if (stolen[mid]==target){
                cnt++;
                break;
            }
            else if(stolen[mid] < target) lo = mid + 1;
            else hi = mid - 1;
        }
    }
 
    cout << cnt;
    return 0;
}

Now we analyse our code. The built-in sorting algorithm in C++ is Quicksort, which has time complexity O(n\log_2 n). Next we already knew that the time complexity of Binary Search Algorithm is O(\log_2 n). So, we end up in a time complexity of O(n\log_2 n + m\log_2n), which is still better than O(n^2).

Advertisements
UOJ Passport Checking : Binary Search Method

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s