b_acs
asked on
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!!
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
>> 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/
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/
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.
ASKER
"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.
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.
>> 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 ?
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 ?
ASKER
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.
*/
I didn't notice the attachment :)
And what is the input you give ?
And what is the input you give ?
ASKER
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"
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"
ASKER
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
But the results on this "flash" as well
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
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.
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
ASKER
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.....
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.....
ASKER
I'm posting a new question to get help with this search.
I can't figure out what is wrong.
I can't figure out what is wrong.
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++.
ASKER
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?
ASKER
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.
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.
>> 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.
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;
}
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 ?