Trying To Match 2 Arrays With Different Elements & Assigned String Literals

[leewilliam236]

I have a binary search and am comparing an array called keyword with 84 elements and a second array called unsorted_dictionary containing 16000 elements. The binary search will pass the two arrays. First it will search for the unsorted_dictionary array to see if its values match up with the keywords array. Once the elements match, it will return a value or do something like that. I will output the keywords array after I've searched and print out whether or not the keywords elements match with the unsorted_dictionary array's elements. (The output box.)

If you're confused here's the entire assignment.
http://voyager.deanza.edu/~bentley/cis22b/ass2.html

/**

Name: William Lee
Compiler: GNU GCC Compiler
Assignment #2

*/

#include <iostream>
#include <fstream>
#include <iomanip>
#include <string>
#include <cstdlib>

using namespace std;

void assign_array(const int, string[], int, ifstream&);
void selectionSort(const int, string[], ifstream&);
int binarySearch(const int, const int, string[], string[], ifstream&, ifstream&, int);
//void output(ofstream, string[], int);
    const int SIZE1 = 84;
    const int SIZE2 = 16000;
int main(){

    ifstream infile1, infile2;
    ofstream outfile;
    infile1.open("keywords.txt");
    infile2.open("unsorted_dictionary.txt");
    outfile.open("output.txt");
    string dummy;
    string keywords[SIZE1], unsorted_dictionary[SIZE2] ;
    int sizee = sizeof(keywords) / sizeof(int);
    int i = 0, j = 0;

if (infile1 && infile2){
    assign_array(SIZE1,keywords,i, infile1);
    assign_array(SIZE2,unsorted_dictionary,j, infile2);
    selectionSort(SIZE1,keywords, infile1);
    selectionSort(SIZE2,unsorted_dictionary, infile2);
    binarySearch(SIZE1, SIZE2, keywords, unsorted_dictionary, infile1, infile2, sizee);
    for (i = 0; i < SIZE1 ; i++){
        if (keywords[i] == 0){
            cout << "Keyword found: " << endl;
        }
        else{
            cout << "Keyword not found: " << endl;
        }
    }
    outfile.close();
        return 0;
}

else{
    cout << "Error Running File";
    exit(1);
}
}

void assign_array(const int size_of_array, string areee[], int counter, ifstream& file){
    while(counter < size_of_array && file >> areee[counter]){
        counter++;
    }
}

void selectionSort(const int size_of_array, string areee[], ifstream& file)
{
    int minIndex;
    for (int i = 0; i < size_of_array - 1; i++)
    {
        minIndex = i;
        for (int j = i+1; j < size_of_array; j++)
        {
            if (areee[j] < areee[minIndex])
            {
                minIndex = j;
            }
        }
        if(minIndex != i) {
            swap(areee[i],areee[minIndex]);
        }
    }
}
int binarySearch(const int size_of_array1, const int size_of_array2, string areee1[], string areee2[], ifstream &file1, ifstream &file2, int sizer)
{
    //int searchValue = areee1[];
    int low, high, middle;
    low = 0;
    high = size_of_array2-1;
    int i = 0;

    for (i = 0; i < size_of_array1; i++){
          while (low <= high){
            middle = (low + high) / 2;
            if (areee2[middle] <= areee1[middle]){
                high = middle - 1;
            }
            else if (areee2[middle] >= areee1[middle]){
                low = middle + 1;
            }
            else{
                return 0;
            }
        }
    }
    return -1;
}

The output should look something like this.

keyword not found: alignas
keyword not found: alignof
keyword not found: and_eq
keyword not found: asm
keyword not found: bitand
keyword not found: bitor
keyword not found: char16_t
keyword not found: char32_t
keyword not found: compl
keyword not found: const_cast
...

Number of keywords not found = ??

[ne555]

¿so what's the problem?


> void selectionSort(const int, string[], ifstream&);
¿why does it need a file as a parameter?

> void assign_array(const int size_of_array, string areee[], int counter, ifstream& file)
¿should `counter' be a parameter?

    for (i = 0; i < SIZE1 ; i++){
        if (keywords[i] == 0){
            cout << "Keyword found: " << endl;
        }

`keywords[i]' is a string. I may contain "alignof", ¿why are you comparing it against 0? ¿what does that mean?

int binarySearch(const int size_of_array1, const int size_of_array2, string areee1[], string areee2[] /*¿two arrays?*/, ifstream &file1, ifstream &file2 /*¿what for?*/, int sizer /*¿?*/)
consider bool binarySearch(const int size, string array[], string value); instead
then you may do

for(int K=0; K<keyword_size; ++K)
   if(not binarySearch(dict_size, dictionary, keyword[K]))
      std::cout << keyword[K] << " not found\n";

By the way, once you do selectionSort(SIZE2,unsorted_dictionary, infile2); `unsorted_dictionary' would not be unsorted, that name is misleading.

[Handy Andy]

Hello leewilliam236,

Everything works until you reach "binarySearch".

At the beginning of main I would check to make sure the files are open.

In addition to what ne555 said. In "binarySearch" function you are passing two file streams that are not used. What are they for and why do you need them? The search loop is not right. You are trying to compare one element of an 84 element array to what is in a 16000 element array using the same subscript variable for both. So trying to access the "keywords" array as areee1[middle], size 84, which is the same as areee1[7999] does not work because his outside the bounds of the array of 84.

Either I am missing something, because the function does not work, because I see nothing to check when the two arrays are equal.

The function returns an "int", but you never put the return value into anything i main for later use.

Another option is not to call "binarySearch" before the for loop, but in the for loop and make use of the return value. I am think of something like this:

for (i = 0; i < SIZE1; i++)
{
	if (1/*or 0/* == binarySearch(SIZE1, SIZE2, keywords[i], unsorted_dictionary))
	{
		cout << "Keyword found: " << endl;
                //  Could expand on this later.
	}
	else
	{
		cout << "Keyword not found: " << endl;
                //  Could expand on this later.
	}
} */

This means the "binarySearch" parameters will need to be changed, i.e., "(int, int, string, array)" and "binarySearch" will need changed to search the dictionary and compare it to the string.

Hope that helps,

Andy

[leewilliam236]

@ne555

why does it need a file as a parameter?
I'm supposed to sort it alphabetically to make sure that the output prints it alphabetically.

should `counter' be a parameter
Yes.

keywords[i]' is a string. I may contain "alignof", ¿why are you comparing it against 0? ¿what does that mean?
I'm not sure. I want to make a conditional where if array1 and array2 contain the same value even though both values are stored in different array addresses, then it should print Keyword Found: keyword[i].

Hope this clarifies your confusion.

[leewilliam236]

@Handy Andy.

In addition to what ne555 said. In "binarySearch" function you are passing two file streams that are not used. What are they for and why do you need them?

Comparing the two files. I want the unsorted_dictionary array to search for the keywords array. If they match, the keyword array will return with "Keyword Found: " Keyword.

Any other questions, feel free to reply.

[Handy Andy]

Hello leewilliam236,

Comparing the two files. I want the unsorted_dictionary array to search for the keywords array. If they match, the keyword array will return with "Keyword Found: " Keyword.

I understand that, but till you are comparing two different arrays not files. The file streams in the "binarySearch" are not need or used.

The "binarySearch" function is not right. There is no way of telling if two strings are equal. It took me awhile, do to a stupid mistake, but I came up with this:

int binarySearch(const int size_of_array1, const int size_of_array2, string checkWord, string sortedDictonary[])
{
	//int searchValue = areee1[];
	int low, high, middle;
	low = 0;
	high = size_of_array2 - 1;
	int i = 0;

	for (i = 0; i < size_of_array1; i++)
	{
		while (low <= high)
		{
			middle = (low + high) / 2;
			
			if (sortedDictonary[middle] == checkWord)
				return middle;
			else if (sortedDictonary[middle] > checkWord)
			{
				high = middle - 1;
			}
			else
			{
				low = middle + 1;
			}
		}
	}
	return 0;
}

and this in main:

for (i = 0; i < SIZE1; i++)
{
	if (binarySearch(SIZE1, SIZE2, keywords[i], unsorted_dictionary))
	{
		cout << "Keyword found: " << i << ' ' << keywords[i] << endl;
        }
	else
	{
		cout << "Keyword not found: " << i << ' ' << keywords[i] << endl;
                // More code needed here and after the for loop.
	}
}

As long as "binarySearch" returns a number greater than zero the word is found.

Just about there. Be sure to check the program requirements.

Hope that helps,

Andy

[ne555]

>> why does it need a file as a parameter?
> I'm supposed to sort it alphabetically to make sure that the output prints it alphabetically.
the content of the file is already loaded into the array, there is no need to pass the stream (which, by the way, is invalid at that point)
forget about the big problem and concentrate on the task ahead: you need to sort an array, period.

>> should `counter' be a parameter
> Yes.
consider

void assign_array(const int size_of_array, string areee[], ifstream& file){
    int counter = 0;
    while(counter < size_of_array && file >> areee[counter]){
        counter++;
    }
}

¿what do you gain with `counter' being a parameter?


about Handy Andy's code

int binarySearch(const int size_of_array1, const int size_of_array2 /*¿? there is only one array*/, string checkWord, string sortedDictonary[])
{
	//int searchValue = areee1[];
	int low, high, middle;
	low = 0;
	high = size_of_array2 - 1;
	int i = 0;

	for (i = 0; i < size_of_array1; i++) //¿what's this loop for?
	{
		while (low <= high)
		{
			middle = (low + high) / 2;
			
			if (sortedDictonary[middle] == checkWord)
				return middle; // <---
			else if (sortedDictonary[middle] > checkWord)
			{
				high = middle - 1;
			}
			else
			{
				low = middle + 1;
			}
		}
	}
	return 0; // <---
}

if the word is found, you return its index, which is stored in `middle'
else, you return.
the problem is that the word may be the first one on the array, so it will be found and `middle' will have 0, making it indistinguishable from the not found case

to fix that, you may return -1 in the not found case, or drop the index and just return a boolean, after all we have modified the initial order of the array.

[Handy Andy]

@ne555

Thank you for pointing that out. I have the feeling my brain was thinking of something else at the time and I did not catch that.

Andy