Help understand probems - Binary Search and Sequenital Search

T

Timmy

The bigger problem is with the Binary Search. The program crashes when it's
excuted. and Visual Studio 2005 indicates stack over flow and shows a break
at that function.

Sequential search is working, but I am trying to have it display the number
of comparisons it took to find the number. It keeps displaying "2."


Thank you folks kindly,

T

#include <iostream>
#include <fstream>
#include<iomanip>
#include<cstdlib>

using namespace std;

ifstream inFile;
ofstream outFile;

void SequentialSearch(int isorted[],int size, int target, int &scompares,
bool &found);
void insertionSort(int isort[], int isorted[],int size);
void BinarySearch(int isorted[],int &compares, int first, int last, bool
&found, int target);


int main()
{
const int arraySize = 15;
int unSort[arraySize];
int sorted[arraySize];
int count=0;
int targets[6];
int compareB;
int compareS;
bool findS;
bool findB;
int firstN = 0;
int lastN = arraySize-1;



inFile.open("input3.txt"); //opening input file
if (!inFile)
{
cerr << "Error Opening File" << endl;
system("pause");
EXIT_FAILURE; //stop program on failure
}

outFile.open("output.txt"); //opening input file
if (!outFile)
{
cerr << "Error Opening File" << endl;
system("pause");
EXIT_FAILURE; //stop program on failure
}


for (int i =0;i < arraySize;i++) //Read in the file with the unsorted
numbers
{
inFile >> unSort;

}

for (int j=0;j< 6;j++) // get the search keys
{
inFile >> targets[j];
}


insertionSort(unSort, sorted, arraySize); //call the insertion sort the here

for (int y=0;y < 6; y++)
{
SequentialSearch(sorted, arraySize, targets[y], compareS, findS);
// void SequentialSearch(int isorted[],int size, int target, int
&scompares, bool &found);
BinarySearch(sorted, compareB, firstN, lastN, findB, targets[y]);
// void BinarySearch(int isorted[],int &compares, int first, int last,
int &found, int target);

cout << setw(15)<< "Unsorted Array" << setw(15) << "Sorted Array" <<
endl;
for (int z=0; z< arraySize; z++){
cout << setw(15) << unSort[z] << setw(15)<< sorted[z] << endl;

}
cout << endl << "Target: " << targets[y] << endl;

cout << endl << "Binary Search Found: ";
if (findB == true)
cout << compareB;
else
cout << " Nothing" << endl;

cout << endl << "Sequential search Found: ";
if (findS == true)
cout << compareS << endl;
else cout << " Nothing" << endl << endl;


}


system("pause");

return EXIT_SUCCESS;
}



//insertion sort starts here
void insertionSort(int isort[], int isorted[],int size)
{
int i,j;
bool Done;

for (int k=0; k < size; k++) isorted[k] = isort[k]; // copy numArray(main)
into isort1

for(i=1;i<size;i++)
{

j=i;
Done = false;
while(j>=1 && !Done)

{

if (isorted[j-1] > isorted[j])
swap(isorted[j-1], isorted[j]);
else
Done = true;

j-- ;
}
// end of WHILE loop

} // end of FOR loop
} // end of insertion sort


void SequentialSearch(int isorted[],int size, int target, int &scompares,
bool &found)

{
scompares = 0;
int index;


if (size ==0)
found = false;

else
scompares = 1;
index = 0;

while ((index <size -1) && (isorted[index] != target))
index++;
scompares++;

if (isorted[index] == target)
found = true;
else
found = false;

}


void BinarySearch(int isorted[],int &compares, int first, int last, bool
&found, int target)
{
compares=0;
int middle;
if(first > last)
found = false;

else
compares++;
middle = (first + last)/2;

if (middle == target)
found = true;

else if (middle < target)
BinarySearch(isorted,compares, middle++ , last, found,
target);

else
BinarySearch(isorted,compares, first, middle--, found,
target);

}// end of Binary Search


/*void print(int isort[], int isorted[], int size, int count, int bfound,
int sfound, int target)
{
outFile << " Unsorted List Insertion Sorted" << endl;

for (int k =0;k < size;k++)
outFile << setw(15) <<isort[k] << setw(16) << << setw(20) << isorted[k]
<< endl;
outFile << endl << "Target: " << setw(23) << target << endl;
outFile << "Binary Search Found: " << found << endl;
outFile << "Sequential Search Found: " <<

}// end of print function */
 
?

=?ISO-8859-1?Q?Erik_Wikstr=F6m?=

The bigger problem is with the Binary Search. The program crashes when it's
excuted. and Visual Studio 2005 indicates stack over flow and shows a break
at that function.

Sequential search is working, but I am trying to have it display the number
of comparisons it took to find the number. It keeps displaying "2."

Try stepping through the code to find out what is going on.
 
C

cringecoder

The bigger problem is with the Binary Search. The program crashes when it's
excuted. and Visual Studio 2005 indicates stack over flow and shows a break
at that function.

Sequential search is working, but I am trying to have it display the number
of comparisons it took to find the number. It keeps displaying "2."

Thank you folks kindly,

T

In your sequential search:

while ((index <size -1) && (isorted[index] != target))
index++;
scompares++;

There's no curly braces, so it's really doing this

while ((index <size -1) && (isorted[index] != target))
{
index++;
}
scompares++;

It only looks like it should work because of your indentation. When
there's no curly braces, only the next statement is executed as part
of the while.

All you'd need to do is

while ((index <size -1) && (isorted[index] != target))
{
index++;
scompares++;
}


Your binary search...
In order for it to not crash, you want to wrap the first else in curly
braces, which would make it...

if(first > last)
found = false;
else
{
// ... The rest of the function body, just like it was
}

Without the curly braces, even if first > last, it'll still recurse as
long as middle != target.
After fixing the crash, the binary search still has an issue, but I
don't know if you still want to try and figure it out yourself or not.
But good luck!

-Dan
 
T

Timmy

The bigger problem is with the Binary Search. The program crashes when
it's
excuted. and Visual Studio 2005 indicates stack over flow and shows a
break
at that function.

Sequential search is working, but I am trying to have it display the
number
of comparisons it took to find the number. It keeps displaying "2."

Thank you folks kindly,

T

In your sequential search:

while ((index <size -1) && (isorted[index] != target))
index++;
scompares++;

There's no curly braces, so it's really doing this

while ((index <size -1) && (isorted[index] != target))
{
index++;
}
scompares++;

It only looks like it should work because of your indentation. When
there's no curly braces, only the next statement is executed as part
of the while.

All you'd need to do is

while ((index <size -1) && (isorted[index] != target))
{
index++;
scompares++;
}


Your binary search...
In order for it to not crash, you want to wrap the first else in curly
braces, which would make it...

if(first > last)
found = false;
else
{
// ... The rest of the function body, just like it was
}

Without the curly braces, even if first > last, it'll still recurse as
long as middle != target.
After fixing the crash, the binary search still has an issue, but I
don't know if you still want to try and figure it out yourself or not.
But good luck!



Hi Dan.
Thanks a lot for the assistance.

I added the curly braces as indicated and it still crashes at the Binary
Search function.

Still lost.

T
 
C

cringecoder

In your sequential search:
while ((index <size -1) && (isorted[index] != target))
index++;
scompares++;
There's no curly braces, so it's really doing this
while ((index <size -1) && (isorted[index] != target))
{
index++;
}
scompares++;
It only looks like it should work because of your indentation. When
there's no curly braces, only the next statement is executed as part
of the while.
All you'd need to do is
while ((index <size -1) && (isorted[index] != target))
{
index++;
scompares++;
}
Your binary search...
In order for it to not crash, you want to wrap the first else in curly
braces, which would make it...
if(first > last)
found = false;
else
{
// ... The rest of the function body, just like it was
}
Without the curly braces, even if first > last, it'll still recurse as
long as middle != target.
After fixing the crash, the binary search still has an issue, but I
don't know if you still want to try and figure it out yourself or not.
But good luck!

Hi Dan.
Thanks a lot for the assistance.

I added the curly braces as indicated and it still crashes at the Binary
Search function.

Still lost.

T



I forgot to mention that middle++ and middle-- in the recursive calls
need to be switched to middle + 1 and middle - 1. That and the curly
braces together will let it run without crashing.

Sorry for forgetting!!!
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top