Returning Values Form Binary Search

[optimus203]

Hey everyone. I'm reading data from a file and putting that data into a vector of pointers. I'm doing a quicksort on vector, asking user for a date search, then returning match via binary search if a match exists. From testing I can see that the values are being properly passed through binary search, but the print function isn't returning properly (although print() does function properly when initially extracting data from text file).

Binary Search function

Appointment Appointment::binary_search(vector<Appointment*> vec, int from, int to, Date user_date_search)
{
  int mid = (from + to) / 2;

  if (vec[mid]->get_month() == user_date_search.month_get()
      && vec[mid]->get_day() == user_date_search.day_get()
      && vec[mid]->get_year() == user_date_search.year_get())
      return *vec[mid];
  else if (vec[mid]->get_year() < user_date_search.year_get()
      || (vec[mid]->get_year() == user_date_search.year_get() && vec[mid]->get_month() < user_date_search.month_get())
      || (vec[mid]->get_year() == user_date_search.year_get() && vec[mid]->get_month() == user_date_search.month_get() && vec[mid]->get_day() < user_date_search.day_get()))
      return binary_search(vec, mid + 1, to, user_date_search);
  else
      return binary_search(vec, from, mid - 1, user_date_search);
}

Print function:

void Appointment::print()
{
  cout << appRead << endl; // funciton that reads data from text file
  cout << "Date: " << monthRead << "/" << dayRead << "/" << yearRead << endl;
  cout << "Time: " << hourRead << ":" << minuteRead << endl;
  cout << "Description: " << descriptionRead << endl;
  cout << "Priority: " << priorityRead << endl;
}

Binary search funciton in main()

Date search_date(mm,dd,yy); // mm, dd, and yy are from user input
Appointment* search_matching_app = new Appointment;
search_matching_app->binary_search(print_apps, 0, print_apps.size(), search_date);

[clanmjc]

Is the sort criteria sorting by pointer or by year month day?

[rollie]

I would highly recommend changing the signature to 'binary search(const vector & vecAppointments)', as currently you are copying the vector everytime you call the function (potentially lots of unnecessary overhead). Also, naming your vectors 'vec' isn't the best policy, as it really doesn't provide the reader much information.

That said, clanmjc is likely correct - if you simply call quicksort on your vector of appointments, it is going to sort the pointers (i.e., memory addresses), rather than your appointments. See http://www.cplusplus.com/reference/clibrary/cstdlib/qsort/, note the 'compare' function they are using. You will need something like that. Also, as luck would have it, STL already has a binary search function! http://www.cplusplus.com/reference/algorithm/binary_search/ You'll need the compare function you wrote for the sort to make it work though.

[optimus203]

Thanks for the reply guys. The sort is sorting pointers to objects that contain month, day, and year data.

So my objects are created in main like so

// example for 2 appointments
Appointment app1, app2,

// == part are markets in the text file that populate_app is reading from
app1.populate_app("==1");
app2.populate_app("==2");

vector<Appointment*> print_apps(2);
print_apps[0] = &app1;
print_apps[1] = &app2;

I also added testing in my binary_search function to make sure the data is being read properly as it progresses through the search - and it is being read fine. Just not printing from the print() call in main.

Date search_date(mm,dd,yy);
Appointment* search_matching_app = new Appointment;
search_matching_app->binary_search(print_apps, 0, print_apps.size(), search_date);
cout << "Appointments found:\n";
search_matching_app->print();

[clanmjc]

Show me the sort predicate you are using for the sort.

Show me the call to the print function.

Is it the same print function that also reads in the file? Are you calling this twice?

[optimus203]

The call to the print function is in the last line of the code above:
search_matching_app->print();

This is the same print function that reads from the file. I called the same print() function to return the sorted vector after I ran the quicksort, so I'm assuming it would work fine when I'm try to return the match from the binary_search().

My quicksort function declaration is like so - this works fine, so I'm not sure it has any influence on the binary_search function.

template <typename T>
Qsort<T>::Qsort(vector<Appointment*> &vec, int left, int right) {}

[clanmjc]

>

This is the same print function that reads from the file.

This is where I am puzzled, do you literally mean reading from the file? If it is the same is it not reading from the file again? If it is reading again, is it messing up your container?

So the Qsort is your own algorithm?

[optimus203]

The Qsort is my own - yes. Once it runs, I can see that the appointment (being read from the text file) have been sorted properly.

I'm calling the print() function:
1 - to print out appointments that are read from file (to check and make sure that read is doing everything it should)
2 - to print out the appointments that have been sorted after the Qsort is run
3 - to print out matching results form binary_search (which isn't functioning)

Theoretically, if the print() function is working in 1 and 2, shouldn't it work in 3?

[clanmjc]

Thanks for the reply, it answered some of my questions. See before, the wording you used I thought the print function was also actually reading the data, it looks like this isn't the case.

Assuming 1 and 2 do work, the print function is working as intended, because it only prints. Let's go ahead and make it a const function.

void Appointment::print() const

Now, as far the binary search, it appears to do what you need it to do. What happens when you debug it and pass in a search value. Does it recursively split your data correctly and find the search value? Can you take us through one debug session...

Your binary search returns a copy of an appointment, from the code you posted you do not assign this copy to anything, so when you call print you call it on what?

Nothing returned here:
search_matching_app->binary_search(print_apps, 0, print_apps.size(), search_date);

Also inside your print function I'm assuming those are member variable, but member variables to what?