Help understand probems - Binary Search and Sequenital Search

Discussion in 'C++' started by Timmy, Jul 7, 2007.

  1. Timmy

    Timmy Guest

    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 */
    Timmy, Jul 7, 2007
    #1
    1. Advertising

  2. On 2007-07-07 04:32, Timmy wrote:
    > 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.

    --
    Erik Wikström
    =?ISO-8859-1?Q?Erik_Wikstr=F6m?=, Jul 7, 2007
    #2
    1. Advertising

  3. Timmy

    Guest

    On Jul 6, 10:32 pm, "Timmy" <> wrote:
    > 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:

    On Jul 6, 10:32 pm, "Timmy" <> wrote:
    >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
    , Jul 7, 2007
    #3
  4. Timmy

    Timmy Guest

    <> wrote in message
    news:...
    > On Jul 6, 10:32 pm, "Timmy" <> wrote:
    >> 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:
    >
    > On Jul 6, 10:32 pm, "Timmy" <> wrote:
    >>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
    >
    > -Dan
    >
    Timmy, Jul 7, 2007
    #4
  5. Timmy

    Timmy Guest

    "Erik Wikström" <> wrote in message
    news:LvKji.3629$...
    > On 2007-07-07 04:32, Timmy wrote:
    >> 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.
    >
    > --
    > Erik Wikström


    thanks for the input

    T
    Timmy, Jul 7, 2007
    #5
  6. Timmy

    Guest

    On Jul 7, 1:42 pm, "Timmy" <> wrote:
    > <> wrote in message
    >
    > news:...
    >
    >
    >
    > > On Jul 6, 10:32 pm, "Timmy" <> wrote:
    > >> 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:

    >
    > > On Jul 6, 10:32 pm, "Timmy" <> wrote:
    > >>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
    >
    >
    >
    > > -Dan


    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!!!
    , Jul 9, 2007
    #6
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Andy
    Replies:
    1
    Views:
    355
    Jack Klein
    Nov 25, 2003
  2. chema15

    Timing probems

    chema15, Sep 4, 2008, in forum: VHDL
    Replies:
    0
    Views:
    494
    chema15
    Sep 4, 2008
  3. Replies:
    9
    Views:
    452
    Keith Thompson
    Jul 3, 2009
  4. Bogdan

    Binary tree search vs Binary search

    Bogdan, Oct 18, 2010, in forum: C Programming
    Replies:
    22
    Views:
    3,060
    Michael Angelo Ravera
    Oct 21, 2010
  5. Jimmy

    Probems with Replace Command

    Jimmy, Sep 3, 2005, in forum: ASP General
    Replies:
    2
    Views:
    101
    Jimmy
    Sep 5, 2005
Loading...

Share This Page