[Webinar] Learn how to a build a cloud-first strategyRegister Now

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 211
  • Last Modified:

Looking for Tips on improving BinarySearch Function

Here is a complete C++ program that my team and I have come up with.  We have an issue with the Search option, though.  I'm not sure how to explain what I am talking about, but I'll try.  When the user chooses Search and searches for a name, the result flashes first.  I can't figure out how to fix it. I am posting the code snippet for the binary search functions and posting the entire program as an attached text file.  Please tell me why my search is flashing at me and how to fix it.

Also:  If you have any tips or suggestions on anything else, I would be happy to hear them!!
void Binaryswap(char searchfor[1][length], char Name[size][length], int &Middle, int &High, int &Low)
{
	while((strncmp (Name[Low], Name[High], length) <= 0) && (strncmp (searchfor[0] ,Name[High], length) <= 0))
	{
		
		Middle = (High + Low) / 2;
		
		if(strncmp (searchfor[0] ,Name[Middle], length) == 0)
		{
			system("cls");
			cout << "The search found \"" << Name[Middle] << "\" You Entered: " << searchfor[0] << endl;
			break;
		}
		else
		{			
			if(strncmp (searchfor[0] ,Name[Middle], length) < 0)
			{
				High = Middle - 1;
				Binaryswap(searchfor, Name, Middle, High, Low);
			}
			else
			{
				Low = Middle + 1;
				Binaryswap(searchfor, Name, Middle, High, Low);
			}
		}
	}
	
	if(strncmp (searchfor[0] ,Name[Middle], length) != 0)
	{
		system("cls");
		cout << "End of Search nothing found!" << endl;
	}
}// end of function Binaryswap
 
void BinarySearch(char Name[size][length])
{ 
	Sort(Name);   
	int High = size - 1;
	int Low = size - 10;
	
	char searchfor[1][length] = {"none"};
	int	Middle = 0;
 
	cout << "Enter the Name you are searching for: " << endl;
	cin >> searchfor[0];
 
	
		Binaryswap(searchfor, Name, Middle, High, Low);
		system("pause");
}// end of function BinarySearch

Open in new window

CIS242-Pgrm2.txt
0
b_acs
Asked:
b_acs
  • 9
  • 4
  • 4
1 Solution
 
Infinity08Commented:
Change the cin way of inputting to a more robust way of inputting, like fgets. cin leaves all unread characters on the stream, which can mess up all later inputs.

        http://www.cplusplus.com/reference/clibrary/cstdio/fgets.html


Can you also explain what you mean by "flashing" ? Could the system("cls") you have explain that ?
0
 
evilrixSenior Software Engineer (Avast)Commented:
>> If you have any tips or suggestions on anything else, I would be happy to hear them!!
Use the STL std::binary_search? It's bound to be faster, and more robust.
http://www.cplusplus.com/reference/algorithm/binary_search.html

You can use std::sort to prepare your data for searching
http://www.cplusplus.com/reference/algorithm/sort.html


You might also want to consider swapping fixed size arrays for vectors and strings
http://www.cplusplus.com/reference/stl/vector/
http://www.cplusplus.com/reference/string/string/
0
 
evilrixSenior Software Engineer (Avast)Commented:
Also, another small observation (a little picky, but) try to avoid passing compiler intrinsics by reference as it's quite inefficient (e.g. High, Middle, Low). It hinders compiler optimization techniques. You'd be better off having a struct to hold these related values and passing the struct by reference. It'd also make the code more simpler to maintain as well as making it a little simpler to read.
0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
b_acsAuthor Commented:
"Can you also explain what you mean by "flashing" ? Could the system("cls") you have explain that ?"

What I mean is that when the user does a search, the results actually flash 3 to 4 times before staying solid.  It's like a loop that is clearing the screen and redisplaying the exact same output.  The search is logically sound as far as I can tell. (I mean it gets the right results every time.)  It's just the flashing.....

Also I don't understand how to use fgets when there is no input file.
0
 
Infinity08Commented:
>> Also I don't understand how to use fgets when there is no input file.

You mean get the input from standard input ? Then just use stdin as the file pointer.


>> What I mean is that when the user does a search, the results actually flash 3 to 4 times before staying solid.

Can you post the entire code ?
0
 
b_acsAuthor Commented:
I posted it in a text file as an attachment but if you don't want to open that then here:


// CIS242-Pgrm2.cpp : Defines the entry point for the console application.
//***************************************************************************************
// Brian Acs
// Ryan Boos
// Michael Berendzen
// Mitchell Boessen
// November 13, 2008
// CIS242-Pgrm2
// CISS242
//***************************************************************************************
// This program allows the user to enter ten names and uses an array of function pointers 
// to call functions for user picked choices on the main menu.
// Also allows user to change, sort, delete, and search for names. 
//***************************************************************************************
 
//***************************************************************************************
//  The include section
//***************************************************************************************
 
#include <iostream>
#include <iomanip>
#include <cstdlib>
 
//***************************************************************************************
//  The namespace section
//***************************************************************************************
 
using namespace std;
 
//***************************************************************************************
//  The global variable declaration section
//***************************************************************************************
 
char ProgramName [] = "CIS242-Pgrm2";		// Used to hold the program name
const int size = 10;
const int length = 25;
char Name[size][length] = {"none","none","none","none","none","none","none","none","none","none"};
 
//***************************************************************************************
//  The function prototype section
//***************************************************************************************
 
void StartUp (void);
void Print(char[size][length]);
void Add(char[size][length]);
void Delete(char[size][length]);
void Update(char[size][length]);
void Sort(char[size][length]);
void swap(char[size][length]);
void BinarySearch(char[size][length]);
void Binaryswap(char[1][length], char[size][length], int&, int&, int&);
void Quit(char[size][length]);
void WrapUp (void);
 
//***************************************************************************************
//  The enumeration section
//***************************************************************************************
 
enum Status {Success, Failure};			// Used to test or return
										// value for program
										// success or failure
 
//***************************************************************************************
//	main
//		This is the entry point for this program.  It controls the flow of execution.
//***************************************************************************************
 
int main(void)
{
	StartUp();
	
	int Option = 0;
		
	void (*fptr[7])(char[size][length]) = {Add, Update, Delete, Sort, BinarySearch, Print, Quit};//declaration creating array of fuction pointers
	
	do 
	{ 
		system("cls");
		cout << "\tMain Menu\n",
		cout << "1) Add\n",
		cout << "2) Update\n",
		cout << "3) Delete\n",
		cout << "4) Sort\n",
		cout << "5) Search\n",
		cout << "6) Print\n",
		cout << "7) Quit\n" << endl;
		
		cout << "Enter Selection: ";
		cin >> Option;
 
		if(Option < 1 || Option > 7)
		{
			cout << "Invalid entry - please re-enter.\n";
			system("pause");
		}		
        else
    	{	
			fptr[Option - 1](Name);
			cout << "\n";
			
		}
 
	}while(Option != 7);
 
	WrapUp();
 
	return Success;	
 
}	//End of function main
 
//***************************************************************************************
//	StartUp
//		Currently this is an empty module or stub.  
//		It will be used to perform any needed initialization
//***************************************************************************************
void StartUp(void)
{
 
}// End of function StartUp
 
//***************************************************************************************
//	Print
//		Displays current array
//***************************************************************************************
void Print(char Name[size][length])
{
	system("cls");
 
	for(int i = 0; i < 10; i++)
	{
		cout << "[" << setw(2) << i + 1 << "] " << Name[i] << endl;
	}
 
	system("pause");
	
}// End of function Print
 
//***************************************************************************************
//	Add
//		Function used to enter names.
//***************************************************************************************
void Add(char Name[size][length])
{
    system("cls");
 
    int Option = 0;
	char Temp[1][length] = {"none"};
    
	for(int i = 0; i < 10; i++)
	{
		cout << "[" << setw(2) << i + 1 << "] " << Name[i] << endl;
    }
	
	cout << "\nEnter the number (1-10) of the line you would like to add a name to: ";
    cin >> Option;
        
    if(Option < 1 || Option > 10)
    {
        cout << "Invalid entry! - Please try again.\n";
                  system("pause");
    }
    else 
    {
		if(strncmp (Name[Option - 1], Temp[0], length) == 0 )
		{
			cout << "\nEnter a First Name: ";
        	cin >> Name[Option - 1];
		}
		else
		{
			cout <<	"\nError! Name already stored! - Please try again.\n";
			system("pause");	
		}
    }
}// End of function Add
 
//***************************************************************************************
//	Delete
//		Function used to delete names from array and 
//      sets the value of elements deleted to back to "none"
//***************************************************************************************
void Delete(char Name[size][length])
{		
	int choice = 0;
	int Option = 0;
	char Temp[1][length] = {"none"};
 
	system("cls");
	
	for(int i = 0; i < 10; i++)
	{
		cout << "[" << setw(2) << i + 1 << "] " << Name[i]<< endl;
	}
	cout << "\nSelect name to delete (1-10): ";
	cin >> Option;
        
    if(Option < 1 || Option > 10)
    {
        cout << "Invalid entry! - Please try again.\n";
        system("pause");
    }
    else
    {
		if(strncmp (Name[Option - 1], Temp[0], length) == 0 )
		{
            cout << "\nError! No name to delete! - Please try again.\n";
            system("pause");
		}
		else
		{	
			cout << "\n\n" << "You are about to delete " << Name[Option-1] << "!\n" << "Are you sure you want to delete this name? \n[1 = Yes or 2 = No]: ";
			cin >> choice;
 
			if(choice == 1)
			{
				strcpy(Name[Option - 1], "none");
			}
			else
			{
			}
		}
	}    		
}  // End of function Delete
 
//***************************************************************************************
//	Update
//		Function used to update/change names
//***************************************************************************************
void Update(char Name[size][length])
{
	int Option = 0;
 
	char Temp[1][length] = {"none"};
		
	system("cls");
		
	for(int i = 0; i < 10; i++)
    {
        cout << "[" << setw(2) << i + 1 << "] " << Name[i]<< endl;
    }
		
	cout << "\nSelect Name to Update (1-10): ";
	cin >> Option;			
		
	if(Option < 1 || Option > 10)
	{
		cout << "Invalid entry! - Please try again.\n";
		system("pause");
	}
	else
	{
		if(strncmp (Name[Option - 1], Temp[0], length) == 0 )
		{
            cout << "\nError! No name to update! - Please try again.\n";
            system("pause");
		}
		else
		{
			cout << "\nEnter new name: ";
			cin >> Temp[0];
			strcpy(Name[Option - 1], Temp[0]);
		}
	}	
}         // End of function Update
 
//***************************************************************************************
//	Sort  
//		Function used to sort names alphabetizing them
//***************************************************************************************
void Sort(char Name[size][length])
{
	for(int Pass = 1; Pass < size; Pass++)
	{
		swap(Name);
	}	
} //       End of function Sort
 
//***************************************************************************************
//	swap  
//		Function used to sort names alphabetizing them 
//***************************************************************************************
void swap(char Name[size][length])
{
	for(int i = 0; i < size - 1; i++)
	{
		if(strncmp(Name[i], Name[i + 1], length) > 0)
		{
			char hold[1][length] = {"none"};
 
			strcpy(hold[0], Name[i]);
			strcpy(Name[i], Name[i + 1]);	
			strcpy(Name[i + 1], hold[0]);
 
			swap(Name);
		}
	}
}// end of function swap
//***************************************************************************************
//	BinarySwap  
//		Function used to search for a name.
//***************************************************************************************
void Binaryswap(char searchfor[1][length], char Name[size][length], int &Middle, int &High, int &Low)
{
	while((strncmp (Name[Low], Name[High], length) <= 0) || (strncmp (searchfor[0] ,Name[High], length) <= 0))
	{
		
		Middle = (High + Low) / 2;
		
		if(strncmp (searchfor[0] ,Name[Middle], length) == 0)
		{
			system("cls");
			cout << "The search found \"" << Name[Middle] << "\" You Entered: " << searchfor[0] << endl;
			break;
		}
		else
		{			
			if(strncmp (searchfor[0] ,Name[Middle], length) < 0)
			{
				High = Middle - 1;
				Binaryswap(searchfor, Name, Middle, High, Low);
			}
			else
			{
				Low = Middle + 1;
				Binaryswap(searchfor, Name, Middle, High, Low);
			}
		}
	}
	
	if(strncmp (searchfor[0] ,Name[Middle], length) != 0)
	{
		system("cls");
		cout << "End of Search nothing found!" << endl;
	}
}// end of function Binaryswap
 
 
//***************************************************************************************
//	BinarySearch  
//		Function used to search for a name after sort functional has operated.
//***************************************************************************************
void BinarySearch(char Name[size][length])
{ 
	Sort(Name);   
	int High = size - 1;
	int Low = size - 10;
	
	char searchfor[1][length] = {"none"};
	int	Middle = 0;
 
	cout << "Enter the Name you are searching for: " << endl;
	cin >> searchfor[0];
 
	
		Binaryswap(searchfor, Name, Middle, High, Low);
		system("pause");
}// end of function BinarySearch
 
//***************************************************************************************
//	Quit 
//		Function used to exit menu/program
//***************************************************************************************
 
void Quit(char Name[size][length])
{
	
} //       End of function Quit
 
//***************************************************************************************
//	WrapUp
//		It is used to perform any end of program processing needed.
//***************************************************************************************
 
void WrapUp(void)
{
	cout << "Program "
		<< ProgramName
		<< " ended successfully."
		<< endl;
}	//	End of function WrapUp
 
/*
Output:
 
Program CIS242-Pgrm2 ended successfully.
*/

Open in new window

0
 
Infinity08Commented:
I didn't notice the attachment :)

And what is the input you give ?
0
 
b_acsAuthor Commented:
The input I give?  

User inputs names.......or not
I noticed now that if the user inputs all 10 names then does a search for the name that is in the fifth position then the results don't "flash"
0
 
b_acsAuthor Commented:
User could input no names and search for a name and get back a result of "nothing found"
But the results on this "flash" as well
0
 
Infinity08Commented:
You call the BinarySwap function recursively - and at every call, it clears the screen and outputs something (often).

As I suggested earlier - get rid of the system("cls")'s and you'll see what's happening a lot more clearly. It's also easier to debug that way.
0
 
b_acsAuthor Commented:
I finally got it!  I will repost the original snippet now corrected.
Thanks for your patience, I know I'm kinda thick headed....
As for your other suggestions - I will try and work on making more robust programs now.

void Binaryswap(char searchfor[1][length], char Name[size][length], int &Middle, int &High, int &Low)
{
	while((strncmp (Name[Low], Name[High], length) < 0) || (strncmp (searchfor[0] ,Name[High], length) < 0))
	{
		Middle = (High + Low) / 2;
        
        if(strncmp (searchfor[0], Name[Middle], length) < 0)
		{
		      High = Middle - 1;
			  Binaryswap(searchfor, Name, Middle, High, Low);
	 	}else
        {
	 	   	Low = Middle + 1;
            Binaryswap(searchfor, Name, Middle, High, Low);
        }
   }     
}  // end of function Binaryswap
 
void BinarySearch(char Name[size][length])
{ 
	Sort(Name);   
	int High = size - 1;
	int Low = 0;
	
	char searchfor[1][length] = {"none"};
	
	int	Middle = 0;
 
	cout << "Enter the Name you are searching for: ";
	cin >> searchfor[0];
 
	if(strncmp (searchfor[0], Name[Middle], length) == 0)
	{
		system("cls");
		cout << "The search found \"" << Name[Middle] << "\" You Entered: " << searchfor[0] << endl;			
	}
	else
    {
        Binaryswap(searchfor, Name, Middle, High, Low);
    }	
			
	if(strncmp (searchfor[0], Name[Middle], length) != 0)
    {
    	system("cls");
        cout << "End of Search nothing found!" << endl;
    }
    else
    {
    } 
		system("pause");
}// end of function BinarySearch

Open in new window

0
 
b_acsAuthor Commented:
Whoops I was wrong!

This fixes the flashing problem, but now I only get correct results for the first element if it matches.
I'm sooo close to having this.....
0
 
b_acsAuthor Commented:
I'm posting a new question to get help with this search.
I can't figure out what is wrong.
0
 
evilrixSenior Software Engineer (Avast)Commented:
You never responded to my suggestion of just using the standard binary search. I'd be interested to know why you are writing your own when there is a perfectly adequate one that is provided with all standard implementations of C++.
0
 
b_acsAuthor Commented:
I obviously have never used the standard binary search.  I have tried to figure out how to use it, but have failed.  In this program, I'm required to use recursion in my sort function and the binary search function.  Can you use the standard that way?
0
 
b_acsAuthor Commented:
I have a secondary question posted called: "How do these binary searches work??"
My program runs now, but if you want to see how I slowly got to a solution, check there.
Again, I'm not sure how to use the standard binary search for the program I had to write; but I'm only 11 weeks old in the programming world.
0
 
evilrixSenior Software Engineer (Avast)Commented:
>> I have tried to figure out how to use it, but have failed
You only had to ask, any expert on here can show you how to use binary_search, it's pretty simple. The link I posted above gives a good example. Did you look?

>> In this program, I'm required to use recursion in my sort function
Why? Is this an academic exercise? If you should make that point clear so the experts here know what level of help to provide you.


// binary_search example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
bool myfunction (int i,int j) { return (i<j); }
 
int main () {
  int myints[] = {1,2,3,4,5,4,3,2,1};
  vector<int> v(myints,myints+9);                         // 1 2 3 4 5 4 3 2 1
 
  // using default comparison:
  sort (v.begin(), v.end());
 
  cout << "looking for a 3... ";
  if (binary_search (v.begin(), v.end(), 3))
    cout << "found!\n"; else cout << "not found.\n";
 
  // using myfunction as comp:
  sort (v.begin(), v.end(), myfunction);
 
  cout << "looking for a 6... ";
  if (binary_search (v.begin(), v.end(), 6, myfunction))
    cout << "found!\n"; else cout << "not found.\n";
 
  return 0;
}

Open in new window

0

Featured Post

Hire Technology Freelancers with Gigs

Work with freelancers specializing in everything from database administration to programming, who have proven themselves as experts in their field. Hire the best, collaborate easily, pay securely, and get projects done right.

  • 9
  • 4
  • 4
Tackle projects and never again get stuck behind a technical roadblock.
Join Now