# Binary search implementation in C++, Help



## invinkoh (Apr 30, 2007)

Assumes all telephone numbers are exactly 8 digits (for simplicity). Given a data file containing a list of telephone numbers with corresponding words, i want to write a program that enable a user to type in one or more 8-digit telephone numbers and retrieve and display the corresponding words.

This program should read in the data file of telephone numbers and associated words (which is ordered on telephone number) and store in a vector of structs (called numwordList).

When the user enters a 8-digit telephone number, the program should perform a binary search of the vector for the entered telephone number and display the associated words (if they exist). The words were generated using the International Standard Keypad.

Sample output which it is going to be like:

Welcome to Telephone Word Finder 


Please enter name of data file : data.txt 

Menu 
1. Enter a telephone number 
2. Quit 

What would you like to do? 1 

Enter 8-digit Telephone Number (without spaces) : 

Words are cachemic,cachemia

Menu 
1. Enter a telephone number 
2. Quit 

What would you like to do? 2 

A definition file telephone.h is attached in the attachment telephone.zip and a sample data file is on attachment as data.txt as well. There should be 2 file which one to be name as telephone.cpp as the implementation file and another would be telewords.cpp as the main program. I am currently stuck at binary search function and also the structs part as I haven't learn enough for that. Any kind of help in developing this small application would be much appreciated. Thanks in advance.


----------



## invinkoh (Apr 30, 2007)

I am still stuck with developing this application. Would someone kind enough to give me a lending hand on this please? This is extremely important for me.


----------



## Shadow2531 (Apr 30, 2001)

What have you accomplished so far?

Are you able to read the data from the file into the struct properly?

How far are you on the binary search part?

For the struct, have you considered using int number instead of string number?

Do you know how to create a struct instance, assign values to its members and then push them back into a vector?

The attachments give you a template of what you need to do, but we need to see what you have so far.


----------



## invinkoh (Apr 30, 2007)

This is what I've done so far. Somehow it contain alot of errors that I dont know how to fix it. Hope anyone could help me in fixing this. Cheers and will be much appreciated.


----------



## Shadow2531 (Apr 30, 2001)

Here's an example of how I did it.


```
#include <iostream>
#include <string>
#include <vector>
#include <stdexcept>
#include <fstream>
#include <algorithm>
#include <iterator>
#include <sstream>
using namespace std;

struct numwords {
    int number;
    string words;
};

int toInt(const string& s) {
    istringstream str(s);
    int i;
    str >> i;
    return i;
};

vector<numwords> getData(const string& filename) {
    ifstream in(filename.c_str());
    if (!in) {
        throw runtime_error("error reading " + filename);
    }
    vector<numwords> temp;
    for (string s; getline(in, s); ) {
        if (!s.empty()) {
            const string::iterator space = find(s.begin(), s.end(), ' ');
            if (space != s.end()) {
                numwords p;
                p.number = toInt(string(s.begin(), space));
                p.words.assign(space + 1, s.end());
                temp.push_back(p);
            }
        }
    }
    return temp;
}

vector<numwords>::const_iterator binsearch(const vector<numwords>& v, const int f) {
    int lo = 0, hi = v.size(), mid;
    while (lo != hi) {
        mid = lo + (hi - lo) / 2;
        if (v[mid].number == f) {
            return v.begin() + mid;
        }
        if (f < v[mid].number) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    return v.end();
}

int main() {
    const vector<numwords> data = getData("data.txt");
    string num;
    getline(cin, num);
    const vector<numwords>::const_iterator found = binsearch(data, toInt(num));
    if (found == data.end()) {
        cout << "number not found" << endl;
        return 1;
    }
    cout << found->words << endl;
}
```
You don't have to read the data in the same way as I did. That's just how I did it (you could use in >> number and in >> words). As for the binsearch, it seems to produce the right result, but I didn't test all situations.


----------

