Binary Search Help.... C++

Cork24

I have a Binary Search... Function and its working fine..
But what i like to be able to do is, have a function inside the code that will find if the user Select Sort or Merge Sort the Array before being allowed to Binary Search the Array..

if the Array was not Sorted then the user will be Showing Error.. This Array was not Sorted please Sort the Array..

Else
Find User.. Etc ...

I would also like to give it a cooler function giving the user a Y/N answer to do you wish the array to be Sorted...

here is my Binary Search
this is inside my MAIN..

{
          //Binary Search Student Records when Select Sort is Done.  
            selectSort(0,N_STUDENT-1);
            cout<<" \n\t Enter the student number to search :";
            cin>>key;
            k=binarySearch(record, 0, N_STUDENT-1, key); 
            if(k>=0)
                cout<<"Student Details with student Number "<<key<<"exists at the position "<<k;
            else
                cout<<"Not found ";
        }

and the Void Function

//function binary search using the key value to serach 
int binarySearch(student  sorted[], int first, int upto, int key) {
    
    while (first < upto) {
        int mid = (first + upto) / 2;  // Compute mid point.
        if (key<sorted[mid].student_number)
        {
            upto = mid;     // repeat search in bottom half.
        } else if (key>sorted[mid].student_number) 
        {
            first = mid + 1;  // Repeat search in top half.
        } else 
        {
            return mid;     // Found it. return position
        }
    }
    return -(first + 1);    // Failed to find key
}

Could do with Help it is the only part i'm Stuck on... i have Stack, Merge,Select etc all working.. just cant get this little fecker to work

Webmonkey

I'm not sure if I understand fully.

In your code you force a select sort before the binary search so it will be sorted?

If you have a menu with options, then when they select to sort it you can set a flag or somethign to say it has been sorted.

You could also maybe, create an IsSorted function that simply iterates over the elements in the array and checks if i+1 is >= i and if not, then the array is not sorted.

Think you will have to phrase it a bit better. It's hard to understand your post unfort.

Cork24

i have menus in the program..

if the person hits binary Search before hitting sort.
i want the program to check to see if the array is sorted our not. if it is then find the search if not give error

Webmonkey

Would it be easier not to have a flag like bool sorted. Then when they do the sort option, you set that to true and then when you do the binary search, you check if this is true and if so allow the binary search.

Cork24

I'm looking at my program now and i dont think a bool function would be right i got something like this but not working

for(int i = 0; i <N_STUDENT.length-1; i++)
if(N_STUDENT[i] > N_STUDENT[i+1]) return false;//> for ascending 
return true;

matrim

There are probably 3 options

1. Implement an isSorted function that you can run on your array, you can then run this as part of the binarySearch function. This will be fine in the small scale but in a large dataset could cause problems

2. Implement a separate sorted boolean flag, that you have to set / unset every time you add to the array or sort the array. This will be awkward to maintain as you add to the program.

3. Write a wrapper around your array class that has functions you have to call to set an element / sort the array. It will then be this wrapper class that is passed to binarySearch and sort. This can internally store a sorted flag so you don't have to worry about forgetting to set the flag as the wrapper will do it for you, and you avoid the overhead of the isSorted function looping through the array.
You also have the option of making the wrapper class always sort after an insert if you want to

It looks like above you are trying to use a variation of the isSorted function option (1). Your function won't work as there is no ".length" for c++ arrays. You should swap to a std::vector, or define / find the size of your array some other way

Cork24

Have you got any Code for them ?

matrim

Cork24 wrote: »

Have you got any Code for them ?

Actually looking at what you've posted it looks like your isSorted code is already using a define to say the size of the array but you are using it wrong.

N_STUDENT is probably defined to be the size of your array so your search should be something like below if in your main

for(int i = 0; i < N_STUDENT; i++)
if(record[i] > record[i+1]) return false;//> for ascending 
return true;

If it's not in your main function "record" should be renamed to the name of the array in that scope.

You can then improve on that by putting it into it's own function and passing in the array and also the size of the array

Cork24

This is my Array...

int x[N_STUDENT];
struct  student
{
    int student_number;              // Student number of student
    string studentname;             // Name of student
    string Address;                //Address of Studnet
    int CourseCode;               //Course Code 
    string CourseName;           // Name of Course 
};
student record[N_STUDENT];


/*****************************************************************************/


int main ()
{    
    
    
    int n,k,key;    
    
    for (n = 0; n < N_STUDENT;n++)
    {

I tried it this way

      {
            for(int i = 0; i < N_STUDENT; i++)
                if(record[i] > record[i+1]) return false;
                   return true;
            //Binary Search Student Records when Merge Sort is Done.
            merge_sort(0,N_STUDENT-1);
            cout<<" \n\t Enter the student number to search :";
            cin>>key;
            k=binarySearch(record, 0, N_STUDENT-1, key); 
            if(k>=0)
                cout<<"Student Details with student Number "<<key<<"exists at the position "<<k;
			else
				cout<<"Not found ";
		}

giving me errors Invalid operands to binary expression ('Student' and 'Student') on this line if(record > record[i+1] return false;

matrim

Cork24 wrote: »

This is my Array...

int x[N_STUDENT];
struct  student
{
    int student_number;              // Student number of student
    string studentname;             // Name of student
    string Address;                //Address of Studnet
    int CourseCode;               //Course Code 
    string CourseName;           // Name of Course 
};
student record[N_STUDENT];


/*****************************************************************************/


int main ()
{    
    
    
    int n,k,key;    
    
    for (n = 0; n < N_STUDENT;n++)
    {

I tried it this way

      {
            for(int i = 0; i < N_STUDENT; i++)
                if(record[i] > record[i+1]) return false;
                   return true;
            //Binary Search Student Records when Merge Sort is Done.
            merge_sort(0,N_STUDENT-1);
            cout<<" \n\t Enter the student number to search :";
            cin>>key;
            k=binarySearch(record, 0, N_STUDENT-1, key); 
            if(k>=0)
                cout<<"Student Details with student Number "<<key<<"exists at the position "<<k;
			else
				cout<<"Not found ";
		}

giving me errors Invalid operands to binary expression ('Student' and 'Student') on this line if(record > record[i+1] return false;

Your student struct doesn't include an overloaded operator>. You need to come up with a way to compare 2 students and see which is less \ greater than the other.

If it's adequate you could just do record.student_number > record[i+1].student_number but the better option would be to overload operator > (or even just create a greaterThan function in your struct)

Cork24

I have select sort and merge sort functions to see which is less then the other but I don't see why I would need a overload function

void merge_sort(int low, int high) { int mid; if(low!=high) { mid =(low+high)/2; merge_sort(low,mid); merge_sort(mid+1,high); merge(low,mid,high); } } void merge (int low, int mid, int high) { int i,j,k ; student b[10]; i=low; j=mid+1; k=low; while((i<=mid)&&(j<=high)) { if(record[i].student_number>=record[j].student_number) { b[k++].student_number=record[j++].student_number; } else { b[k++].student_number=record[i++].student_number; } } while ( i <= mid ) b[k++].student_number = record[i++].student_number; while ( j <= high ) b[k++].student_number = record[j++].student_number; for ( i = low;i <= high;i++ ) record[i].student_number = b[i].student_number;

Webmonkey

The overload function would just be a convenience so you don't have to do record.student_number > record[i+1].student_number but instead record > record[i+1]. The overloaded function would know to compare the student number

Cork24

could you give me a sample of code to what you mean

Webmonkey

http://www.learncpp.com/cpp-tutorial/94-overloading-the-comparison-operators/

Cork24

i have something like this

bool is_sorted(student array[])

while(!is_sorted(record))    choose_a_method_and_sort(record);  do_binary_search(record)

t1mm

You could also maybe, create an IsSorted function that simply iterates over the elements in the array and checks if i+1 is >= i and if not, then the array is not sorted.

Does this not negate the benefits of using the binary search method rather than simply iterating through the array and returning i when the value being searched for is matched (if speed is not a problem)?

Webmonkey

t1mm wrote: »

Does this not negate the benefits of using the binary search method rather than simply iterating through the array and returning i when the value being searched for is matched (if speed is not a problem)?

Indeed!
It's not ideal at all. One of the preconditions for a binary search is that you guarantee that the array is ordered.

I still think the flag idea is best.

OP, I'm not even sure why you give the option to first sort and then search. Why don't you auto sort anyways.

Cork24

Want to give the user a choice of select sort or merge sort and give them the choice to binary search when its merge or select sorted array I dont want function in a function calling another function speed is being slowed down and user time searching is high

Webmonkey

Cork24 wrote: »

Want to give the user a choice of select sort or merge sort and give them the choice to binary search when its merge or select sorted array I dont want function in a function calling another function speed is being slowed down and user time searching is high

Can you elaborate on what you mean by user search time is high?

I don't mean to call a sort in the binary search function but simply to have it called once before hand and then you can call binary search as often as you like.

I still think by simply setting a flag when you complete a select or merge sort when it has complete. Then check this flag when the user selects binary search. If the flag isn't set, don't allow binary search, otherwise do.

Cork24

Wat I mean by search time high ? The whole point of binary search is when the user enters in a number the search will either go left or right from the root node faster search time even tho you can't really see the difference in speed with so little records. But the sort function goes though the whole array that's my understanding of it anyway

Webmonkey

Cork24 wrote: »

Wat I mean by search time high ? The whole point of binary search is when the user enters in a number the search will either go left or right from the root node faster search time even tho you can't really see the difference in speed with so little records. But the sort function goes though the whole array that's my understanding of it anyway

Yeah that's correct. That's why I think you should use a flag to check rather than use an IsSorted function as this will waste time iterating over the entire array (if it's all sorted even).

Cork24

How do I use a flag on the binary search ?

Webmonkey

Cork24 wrote: »

How do I use a flag on the binary search ?

Something like this maybe?

int main (int argc, char * argv[])
{
 bool bListSorted = false;
 ..
 ..
 do
 {
   ...
   ...
   switch(choice)
   {
      case 0:
       DoMergeSort();
       bListSorted = true;
       break;
      case 1:
       DoSelectionSort();
       bListSorted = true;
       break;
      case 2:
      if (!bListSorted)
       std::cout<< "Sort list first!" << std::endl;
     else
       DoBinarySearch();
    } 
 } while (choice != 0)
...
...
return 0;
}

Cork24

Ok. I will look at that and see what needs to go into do statement and what I come up with

Webmonkey

Cork24 wrote: »

Ok. I will look at that and see what needs to go into do statement and what I come up with

It's just a simple check before you perform a binary search on the list. Should be straight forward.

Cork24

Ok cheers