binary search in array

[G60iz8AR]

How do you find the binary search in the array ? please help

void loadArray( int a[], int &cnt, ifstream &infile )
{
while( cnt < MAX && infile >> a[cnt] )
cnt++;
infile.close(); // Done reading. Close it
}
void printArray( int a[], int cnt )
{
for ( int i=0 ; i<cnt ; i++ )
cout << a[i] << " ";
cout << endl;
}
int bsearch( int a[], int cnt, int target )
{
int lo=0, hi=cnt-1;
while ( lo <= hi )
{
int mid = (lo+hi)/2;

/* if the target # is here at the mid slot
then just return mid. we are done :)

otherwise if target is > a[mid]
set lo to mid+1

otherwise it must be true that target < a[mid]
so, set hi to mid -1
*/
}

// if you make it to here and never returned out of the loop
// then the number must not be in the array
// return NOT_FOUND


return NOT_FOUND; // change as needed
}

[Shren]

I dont think anyones going to answer your question because you are not clear, and neither is anything that you have pasted, without using the code format.

[keskiverto]

The content of the homework hints that you have been explained how binary search algorithm operates. There are a lot of hints in those comments too.

[rodiongork]

You can also find tons of info at internet, for example:

http://codeabbey.com/index/wiki/binary-search

(and by the way here is the link to practice problem about binary search)

[G60iz8AR]

Is this the correct way of doing it ?

void loadArray( int a[], int &cnt, ifstream &infile )
{
while( cnt < MAX && infile >> a[cnt] )
cnt++;
infile.close(); // Done reading. Close it
}
void printArray( int a[], int cnt )
{
for ( int i=0 ; i<cnt ; i++ )
cout << a[i] << " ";
cout << endl;
}
int bsearch( int a[], int cnt, int target )
{
int lo=0, hi=cnt-1;
while ( lo <= hi )
{
int mid = (lo+hi)/2;

return mid = (lo+hi)/2; /* if the target # is here at the mid slot
then just return mid. we are done :)


int target = (mid+1); else > ( a[mid]) otherwise if target is > a[mid]
set lo to mid+1

int target = (mid+1); else < (a[mid]) otherwise it must be true that target < a[mid]
so, set hi to mid -1
*/
}

// if you make it to here and never returned out of the loop
// then the number must not be in the array
// return NOT_FOUND


return NOT_FOUND; // change as needed
}

[keskiverto]

In code tags and with some indentation, and moved comments a bit:

int bsearch( int a[], int cnt, int target )
{
  int lo=0, hi=cnt-1;
  while ( lo <= hi )
   {
    int mid = (lo+hi)/2;

    // if the target # is here at the mid slot
    // then just return mid. we are done :)
    return mid = (lo+hi)/2;

    // otherwise if target is > a[mid]
    // then set lo to mid+1
    int target = (mid+1); else > ( a[mid])

    // otherwise it must be true that target < a[mid]
    // so, set hi to mid -1
    int target = (mid+1); else < (a[mid])

    // call bsearch recursively
   }

  // if you make it to here and never returned out of the loop
  // then the number must not be in the array
  return NOT_FOUND; // What would be a valid, logical value for NOT_FOUND?
}

Comment on line 8 says IF, but there is nothing conditional on line 10.

Target is the value that you are looking for. You should not change it.