Solved

# Looking for Tips on improving BinarySearch Function

Posted on 2008-11-11
206 Views
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
``````
CIS242-Pgrm2.txt
0
Question by:b_acs

LVL 53

Expert Comment

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

LVL 39

Expert Comment

>> 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

LVL 39

Expert Comment

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

Author Comment

"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

LVL 53

Expert Comment

>> 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

Author Comment

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 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 << "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

//***************************************************************************************

//		Function used to enter names.

//***************************************************************************************

{

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

{

system("pause");

}

}

//***************************************************************************************

//	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.

*/
``````
0

LVL 53

Expert Comment

I didn't notice the attachment :)

And what is the input you give ?
0

Author Comment

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

Author Comment

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

LVL 53

Accepted Solution

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

Author Comment

I finally got it!  I will repost the original snippet now corrected.
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
``````
0

Author Comment

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

Author Closing Comment

I'm posting a new question to get help with this search.
I can't figure out what is wrong.
0

LVL 39

Expert Comment

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

Author Comment

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

Author Comment

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

LVL 39

Expert Comment

>> 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))

// using myfunction as comp:

sort (v.begin(), v.end(), myfunction);

cout << "looking for a 6... ";

if (binary_search (v.begin(), v.end(), 6, myfunction))

return 0;

}
``````
0

## Featured Post

IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger.  It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article locâ€¦
Container Orchestration platforms empower organizations to scale their apps at an exceptional rate. This is the reason numerous innovation-driven companies are moving apps to an appropriated datacenter wide platform that empowers them to scale at a â€¦
This tutorial covers a step-by-step guide to install VisualVM launcher in eclipse.
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.