Question

This program will function exactly the same as Ponder 02. It prompt the user for a filename. We will then read the contents of the file into a list. The program will then prompt the user for a name. Finally, we will tell the user whether the name is in the list.

Read From a File

The first part of the program will be to read the contents of a file into a list. This data will be in JSON. For example, the contents of the file languages.json might be:

{
  "array": [
      "C",
      "C#",
      "C++",
      "Java",
      "JavaScript",
      "Kotlin",
      "PHP",
      "Perl",
      "Python",
      "Swift",
      "VB"
  ]
}

Note that the contents of this file are guaranteed to be in sorted order. Of course, if the file does not exist, then a user-friendly message will be displayed to the user.

Advanced Search

Next the program will use the advanced search to determine if the name is in the list. This should behave exactly the same as it did for the linear search in Ponder 02. The only difference is that we will use a much more efficient algorithm to perform the search.

When finished, the program will display a message indicating whether the name was found.

Example

The following example is a single run-through of the program.

What is the name of the file? languages.json
What name are we looking for? C++
We found C++ in languages.json.

Answer 1

The algorithm for search is Binary Search. Linear Search runs in O(n) time while Binary Search runs in O(log n) time. Thus, Binary Search is much much faster than Linear Search. The only condition for binary search is that the data must be sorted. Since the values in the json file are sorted, binary search can be used.A binary search looks at the middle element of the list and compares it with the key. If key is found, then the search terminates, if the middle element is greater than key, then the key cannot lie in the upper half of the list. So the search reduces to lower half and so on.

Read the comments in the code to find how it works:

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

int main()
{
    //Input file name from user
    string filename;
    cout << "What is the name of the file?  ";
    cin >> filename;
    
    //try to open the file
    ifstream fp;
    fp.open(filename);
    //If the file does not open
    if(!fp.is_open()) {
        cout <<"File cannot be opened as filename might be incorrect!";
        return 1;
    }
    
    //A vector of strings; An array can also be used 
    //if the maximum possible number of words is known
    std::vector<string> words;
    string word;
    int flag = 0;
    //Run the loop for each word
    while(fp >> word) {
        //List started
        if(word=="[") {
            flag = 1;
            continue;
        }
        //List ends
        if(word=="]") {
            break;
        }
        //Inside list
        if(flag) {
            //Remove the first "
            word.erase(0,1);
            //Remove the last ,
            word.erase(word.size()-1);
            //Check the last character if it is ", remove it
            if(word[word.size()-1] == '"') word.erase(word.size()-1);
            //Insert the word into the vector
            words.push_back(word);
        }
    }
    
    //Input searchKey
    string searchKey;
    cout <<"What name are we looking for? ";
    cin >> searchKey;
    
    //Implement binary search
    int i = 0, j = words.size()-1;
    int mid;
    int found = 0;
    while(i<=j) {
        mid = i+(j-i)/2;
        if(words[mid]==searchKey) {found = 1; break;}
        else if (words[mid]>searchKey) {j=mid-1;}
        else i=mid+1;
    }
    if(found) cout << "We have found " << searchKey << " in " << filename;
    else cout << searchKey << " is not in the file " << filename;
    return 0;
}

For sample run create a languages,json in the same folder as the C++ program with the followig contents:

{
  "array": [
      "C",
      "C#",
      "C++",
      "Java",
      "JavaScript",
      "Kotlin",
      "PHP",
      "Perl",
      "Python",
      "Swift",
      "VB"
  ]
}

Sample runs:

1.

What is the name of the file?  lang.j                                                                                         
File cannot be opened as filename might be incorrect!  

2.

What is the name of the file?  languages.json                                                                                 
What name are we looking for? C++                                                                                             
We have found C++ in languages.json   

3.

What is the name of the file?  languages.json                                                                                 
What name are we looking for? ABCD                                                                                            
ABCD is not in the file languages.json