Caruso
02-21-07, 07:30 PM
/* Filename: bsearch.cpp
This program creates an array of 100 sorted integers, prints them,
and then allows the user to repeatedly look up items using binary
search. The result of each search (array index where the item was
found or a not found message) is printed on the screen.
Tested with:
Microsoft Visual C++ 6.0
Microsoft Visual C++ .NET
g++ under Linux
*/
#include <cstdlib> // needed for srand, rand, and tolower functions
#include <cctype> // for tolower function
#include <iostream>
#include <iomanip> // needed for setw
using namespace std;
const int MaxArray = 100;
typedef int IntArrayType[MaxArray];
// Function prototypes:
int BinarySearch(IntArrayType IntArray, int Low, int High, int Target);
void LoadArray(IntArrayType IntArray, int Count);
void PrintArray(IntArrayType IntArray, int Count);
void DoSearches(IntArrayType IntArray, int Count);
/* Given: IntArray Array of integers.
Low The low index of the range of integers to search.
High The top index of the range of integers to search.
Target The integer for which to search.
Task: To do a binary search for Target in the specified range of
IntArray.
Return: In the function name, return the index of where Target was
found or -1 if it was not found.
*/
int BinarySearch(IntArrayType IntArray, int Low, int High, int Target)
{
int Mid, Difference;
while (Low <= High)
{
Mid = (Low + High) / 2;
Difference = IntArray[Mid] - Target;
if (Difference == 0) // IntArray[Mid] == Target
return Mid;
else if (Difference < 0) // IntArray[Mid] < Target
Low = Mid + 1;
else
High = Mid - 1;
}
return -1; // If reach here, Target was not found.
}
/* Given: IntArray Array of integers, with the data stored at indices
0 through Count - 1.
Count The number of integers in IntArray.
Task: To print the integers from IntArray, with up to 15 per line.
Return: Nothing.
*/
void PrintArray(IntArrayType IntArray, int Count)
{
int k;
for (k = 0; k < Count; k++)
{
cout << setw(5) << IntArray[k];
if (k % 15 == 14)
cout << endl;
}
cout << endl;
}
/* Given: Count The number of integers to be placed into IntArray.
Task: To place Count sorted integers into IntArray.
Return: IntArray The array of sorted integers.
*/
void LoadArray(IntArrayType IntArray, int Count)
{
int k;
IntArray[0] = 1;
for (k = 1; k < Count; k++)
IntArray[k] = IntArray[k - 1] + (10.0 * rand()) / RAND_MAX + 1;
}
/* Given: IntArray Array of integers, with the data stored at indices
0 through Count - 1.
Count The number of integers in IntArray.
Task: To allow the user to do as many searches as desired for
particular items, with the result of each search printed on
the screen.
Return: Nothing.
*/
void DoSearches(IntArrayType IntArray, int Count)
{
int Num, Position;
char Reply;
do
{
cout << "Enter number to search for: ";
cin >> Num;
Position = BinarySearch(IntArray, 0, Count - 1, Num);
if (Position == -1)
cout << "Not found" << endl;
else
cout << "Found in position " << Position << endl;
cout << endl << "Do another search (y/n)? ";
cin >> Reply;
Reply = tolower(Reply); // convert to lower case
}
while (Reply == 'y');
}
int main(void)
{
IntArrayType IntArray;
LoadArray(IntArray, MaxArray);
PrintArray(IntArray, MaxArray);
DoSearches(IntArray, MaxArray);
return 0;
}
This program creates an array of 100 sorted integers, prints them,
and then allows the user to repeatedly look up items using binary
search. The result of each search (array index where the item was
found or a not found message) is printed on the screen.
Tested with:
Microsoft Visual C++ 6.0
Microsoft Visual C++ .NET
g++ under Linux
*/
#include <cstdlib> // needed for srand, rand, and tolower functions
#include <cctype> // for tolower function
#include <iostream>
#include <iomanip> // needed for setw
using namespace std;
const int MaxArray = 100;
typedef int IntArrayType[MaxArray];
// Function prototypes:
int BinarySearch(IntArrayType IntArray, int Low, int High, int Target);
void LoadArray(IntArrayType IntArray, int Count);
void PrintArray(IntArrayType IntArray, int Count);
void DoSearches(IntArrayType IntArray, int Count);
/* Given: IntArray Array of integers.
Low The low index of the range of integers to search.
High The top index of the range of integers to search.
Target The integer for which to search.
Task: To do a binary search for Target in the specified range of
IntArray.
Return: In the function name, return the index of where Target was
found or -1 if it was not found.
*/
int BinarySearch(IntArrayType IntArray, int Low, int High, int Target)
{
int Mid, Difference;
while (Low <= High)
{
Mid = (Low + High) / 2;
Difference = IntArray[Mid] - Target;
if (Difference == 0) // IntArray[Mid] == Target
return Mid;
else if (Difference < 0) // IntArray[Mid] < Target
Low = Mid + 1;
else
High = Mid - 1;
}
return -1; // If reach here, Target was not found.
}
/* Given: IntArray Array of integers, with the data stored at indices
0 through Count - 1.
Count The number of integers in IntArray.
Task: To print the integers from IntArray, with up to 15 per line.
Return: Nothing.
*/
void PrintArray(IntArrayType IntArray, int Count)
{
int k;
for (k = 0; k < Count; k++)
{
cout << setw(5) << IntArray[k];
if (k % 15 == 14)
cout << endl;
}
cout << endl;
}
/* Given: Count The number of integers to be placed into IntArray.
Task: To place Count sorted integers into IntArray.
Return: IntArray The array of sorted integers.
*/
void LoadArray(IntArrayType IntArray, int Count)
{
int k;
IntArray[0] = 1;
for (k = 1; k < Count; k++)
IntArray[k] = IntArray[k - 1] + (10.0 * rand()) / RAND_MAX + 1;
}
/* Given: IntArray Array of integers, with the data stored at indices
0 through Count - 1.
Count The number of integers in IntArray.
Task: To allow the user to do as many searches as desired for
particular items, with the result of each search printed on
the screen.
Return: Nothing.
*/
void DoSearches(IntArrayType IntArray, int Count)
{
int Num, Position;
char Reply;
do
{
cout << "Enter number to search for: ";
cin >> Num;
Position = BinarySearch(IntArray, 0, Count - 1, Num);
if (Position == -1)
cout << "Not found" << endl;
else
cout << "Found in position " << Position << endl;
cout << endl << "Do another search (y/n)? ";
cin >> Reply;
Reply = tolower(Reply); // convert to lower case
}
while (Reply == 'y');
}
int main(void)
{
IntArrayType IntArray;
LoadArray(IntArray, MaxArray);
PrintArray(IntArray, MaxArray);
DoSearches(IntArray, MaxArray);
return 0;
}