1

Having trouble with the binary_search function listed at the top. not sure where to go with it. I'm not very familiar with binary searching.

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

using namespace std;

void get_input(ifstream& fin, int a[], int size, int & array_size);

void binary_search (int a[], int & array_size)
{
    cout << "Please enter the element you would like to search for \n";
    int element;
    cin >> element;

    int lastindex=array_size-1, startindex=0;

    while (startindex <= lastindex)
    {
        int midindex=(array_size/2);
        if(element > a[midindex])
        {
            startindex=midindex;
        }
        else if (element < a[midindex])
        {
            lastindex=midindex-1;
        }

    }

}

int main()
{
    int array_size=-1;
    int a[100];

    ifstream fin;

    get_input (fin, a, 100, array_size);

    binary_search (a, array_size);

    return 0;
}

void get_input (ifstream& fin, int a[], int size, int & array_size)
{
    fin.open("numbers.txt");
    if (fin.fail())
    {
        cout << "File failed to open";
        exit(1);
    }


    for(int i = 0; i < size; i++)
    {
        a[i] = 0;
    }

    cout << "The numbers in the array are: \n\n";

    for (int i = 0; i < size; i++)
    {
        if (!fin.eof())
        {
            fin >> a[i];
            array_size ++;
        }
    }

    for (int i = 0; i < array_size; i++)
    {
            cout << a[i] << "  ";
    }

    cout << "\n\n\n";
    cout << "The numbers in the array sorted are: \n\n";

   for(int i = 0; i < array_size; ++i )
   {
        int temp2 = a[i];

        for (int j = i+1; j < array_size; ++j )
        {

            if( a[j] < temp2)
            {
                temp2 = a[j];

                int temp = a[i];
                a[i]    = a[j];
                a[j]    = temp;
            }
        }
    }





    for (int i = 0; i < array_size; i++)
    {
            cout << a[i] << "  ";
    }

    cout << "\n\n\n";

    fin.close();
}

when done the program is suppose to take an input from a file assign it to an array then sort the array. After this i need to use a binary search to find a number given by the user and display its place in the array to the user.

update: getting wrong output for the index found.... should i just add one to midindex?

void binary_search (int a[], int & array_size)
{
    cout << "Please enter the element you would like to search for \n";
    int element;
    cin >> element;

    int lastindex=array_size-1, startindex=0;

    while (startindex <= lastindex)
    {
        int midindex= startindex + (lastindex - startindex) / 2;

        if(element > a[midindex])
        {
            startindex=midindex+1;
        }
        else if (element < a[midindex])
        {
            lastindex=midindex-1;
        }
        else if (element == a[midindex])
        {
            cout<<"Element "<<element<<" found at index "<<midindex<<endl;
            return;
        }



    }

}
Improve this question
7
  • 2
    Where to go with it? First of all, you should separate the i/o from the search function, and pass the element to search for as a parameter into the function. Commented Oct 21, 2010 at 3:25
  • Why not use std::vector, std::swap, etc? Commented Oct 21, 2010 at 3:29
  • @GMan cant, have to code it by hand. or i would. Commented Oct 21, 2010 at 3:31
  • @GMan -- Probably the same reason he's not using std::binary_search(homework) Commented Oct 21, 2010 at 3:32
  • @Alec: you keed saying you get the wrong index. Can you show us your test data and the program's output so that we can help instead of guessing? Commented Oct 21, 2010 at 3:36

5 Answers 5

Reset to default
2

Try changing

startindex=midindex;

to:

startindex=midindex + 1;

and

int midindex=(array_size/2);

to

int midindex= startindex + (lastindex - startindex) / 2

and most importantly you are doing nothing when you find the element !!

if(element == a[midindex]) {
  cout<<"Element "<<element<<" found at index "<<midindex<<endl;
  return;
}
Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

yes, i voted down when i saw your answer being startindex=midindex + 1, fixed now :)
this worked perfect except im not getting back the correct midindex.
If the element is present in the array, you should get the right index. Is your element present in the array ?
yea the output numbers are 1, 6, 7, 11, 19, 21..... so on. and when i search for 11 im not getting the correct index.
Also note that the index starts from 0 and not 1. If you want the human style index(starting with 1) you should add 1 to midindex before displaying its value.
2

My first reaction is to change the line

int midindex=(array_size/2);

to

int midindex = startindex + (lastindex - startindex) / 2;

Also, don't you want to report if the sought element was found or not? To detect the case when the element is found, another if branch like the following

if( element == a[midindex] )

can be inserted. That can have a return element; or return midindex inside it coupled with a return failure; outside the loop.

EDIT: I made a casual attempt to write a version of binary search. I don't claim it to be correct, as binary search is (in)famous for getting incorrect. Some code with test cases and output is uploaded at codepad.

Snippet:

int *
mybsearch( int const *  const a, size_t const n, int const key ) {

    int * lo = const_cast< int * >( a );
    int * hi = lo + n;

    while( lo <= hi ) {

        int * const mid = lo + (hi - lo) / 2;
        int const midelem = *mid;

        if( key == midelem ) {
            return mid;
        }
        else if( key < midelem ) {
            hi = mid - 1;
        }
        else {
            lo = mid + 1;
        }
    }

    return NULL;
}

The main and test code:

int main() {

    int const arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90};
    size_t const num = sizeof( arr ) / sizeof( int );

    int * pos20 = mybsearch( arr, num, 20 );
    assert( pos20 && (*pos20 == 20) );

    int * pos25 = mybsearch( arr, num, 25 );
    assert( !pos25 );

    int * pos5 = mybsearch( arr, num, 5 );
    assert( !pos5 );

    int * pos105 = mybsearch( arr, num, 105 );
    assert( !pos105 );
}
Improve this answer

Comments

1

Binary search works nicely as a recursive algorithm. Pass in the array and length, check the middle value, and recurse on the upper / lower half of the array, as appropriate.

Improve this answer

Comments

0

Consider carefully what is not right about int midindex=(array_size/2); when array_size = 1. Then generalize to array_size = 3. Then to any odd number. This will require small run simulations in your head or on paper.

Improve this answer

Comments

0

You're close. You want to do something like this:

int binary_search ...

so you can return the index of the element

while (startindex < lastindex)    
{
    int midindex=(startindex+endindex)/2;
    if(element = a[midindex]) {
        return midindex;
    }
    else if(element > a[midindex])
    {
        startindex=midindex+1;
Improve this answer

1 Comment

The statement int midindex=(startindex+endindex)/2; is susceptible to arithmetic overflow. See googleresearch.blogspot.com/2006/06/… Better is to write something like: int midindex = startindex + (endindex - startindex)/2;

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.