Binary String Search

Using binary search

Page 1 of 1

7 Replies - 11199 Views - Last Post: 29 July 2010 - 07:43 PM Rate Topic: -----

#1 Navaroas  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 7
  • Joined: 29-July 10

Binary String Search

Posted 29 July 2010 - 05:39 PM

Okay, so I am currently working on this problem for homework and have already spent some time simply learning about pointers which actually extends beyond what we have learned so far and something I'm not sure I'm allowed to do, but now that I have the sorting part of the function working, I can't see to get my binary string search to work with the *char arrays. Can anyone help? Here's the code.

 

#include <string>
#include <iostream>
using namespace std;


int binarySearch(char *[], int, string);
void sortArray(char *[], int);

const int SIZE = 20;


int main()
{
   char *name[] = {"Collins, Bill",  "Smith, Bart",  "Michalski, Joe", "Griffin, Jim",
	               "Sanchez, Manny", "Rubin, Sarah", "Taylor, Tyrone", "Johnson, Jill",
	               "Allison, Jeff",  "Moreno, Juan", "Wolfe, Bill",    "Whitman, Jean",
	               "Moretti, Bella", "Wu, Hong",     "Patel, Renee",   "Harrison, Rose",
                   "Smith, Cathy",   "Conroy, Pat",  "Kelly, Sean",    "Holland, Beth"};

	string search;
	int results;

	//Get a name to search for
	cout << "Enter the name you wish to search for: ";
	cin >> search;

	//Sort the names
	sortArray(name, SIZE);

	//Search for the name
	results = binarySearch(name, SIZE, search);

	//If binarySearch returned -1, the name was not found
	if (results == -1)
		cout << "That name does not exist in the array.\n";
	else
	{
		cout << "Name " << search << " was found in element "
			<< results << " of the array.\n";
	}


   return 0;
}

void sortArray(char *string[], const int size)
{
   int pass, i;
   char *temp;

   for (pass=0; pass < size - 1; pass++) 
   {
      for (i=0; i<size - 1; i++) 
	  {
         if (strcmp(string[i], string[i+1]) > 0) 
		 {
            temp = string[i];
            string[i] = string[i+1];
            string[i+1] = temp;
         }
      }
   }
}

int binarySearch(char *string[], int size, int value)
{
	int first = 0,
		last = size - 1,
		middle,
		position = -1;
	bool found = false;

	while (!found && first <= last)
	{
		middle = (first + last) / 2;
		if (string[middle] == value)
		{
			found = true;
			position = middle;
		}
		else if (string[middle] > value)
			last = middle - 1;
		else
			first = middle + 1;
	}
	return position;
}




Is This A Good Question/Topic? 0
  • +

Replies To: Binary String Search

#2 novman  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 41
  • Joined: 03-June 10

Re: Binary String Search

Posted 29 July 2010 - 05:53 PM

on line 65 you have declared value as an int when you are trying to pass a string
Was This Post Helpful? 1
  • +
  • -

#3 Navaroas  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 7
  • Joined: 29-July 10

Re: Binary String Search

Posted 29 July 2010 - 06:07 PM

Thank you. I corrected that and changed the bottom code to this now:

int binarySearch(char *word[], int size, string value)
{
	int first = 0,
		last = size - 1,
		middle,
		position = -1;
	bool found = false;

	while (!found && first <= last)
	{
		middle = (first + last) / 2;
		if (word[middle] == value)
		{
			found = true;
			position = middle;
		}
		else if (word[middle] > value)
			last = middle - 1;
		else
			first = middle + 1;
	}
	return position;
}



The code actually runs now, but when I enter in any of the names I'm not getting the positive result.

This post has been edited by Navaroas: 29 July 2010 - 06:08 PM

Was This Post Helpful? 0
  • +
  • -

#4 novman  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 41
  • Joined: 03-June 10

Re: Binary String Search

Posted 29 July 2010 - 06:18 PM

write a for loop that prints out the sorted data n see what it prints
Was This Post Helpful? 0
  • +
  • -

#5 Navaroas  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 7
  • Joined: 29-July 10

Re: Binary String Search

Posted 29 July 2010 - 06:29 PM

If placing loop

for (int i = 0; i < SIZE; i++)
	{
		cout << name[i] << endl;
	}



right after sortArray function call, then everything seems to show as it should.
Was This Post Helpful? 0
  • +
  • -

#6 novman  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 41
  • Joined: 03-June 10

Re: Binary String Search

Posted 29 July 2010 - 06:36 PM

ok, so you are definitely typing in the name correctly? i think it might have something to do with your string comparisons...
Was This Post Helpful? 0
  • +
  • -

#7 novman  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 41
  • Joined: 03-June 10

Re: Binary String Search

Posted 29 July 2010 - 07:04 PM

try this:


    string search;
    int results;

    //Get a name to search for
    cout << "Enter the name you wish to search for: ";
    //cin >> search;
    getline(cin, search);

    //Sort the names
    sortArray(name, SIZE);



it wasnt getting the whole name, only the first string when using just cin >> search;
Was This Post Helpful? 1
  • +
  • -

#8 Navaroas  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 7
  • Joined: 29-July 10

Re: Binary String Search

Posted 29 July 2010 - 07:43 PM

Ah. It works perfectly now. Thank you very much.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1