[amyceres]

So I took the easier way to making this program work by using case statement...but I know that I should probably used binary search for this ...since files are never this small. How is it done? Binary Searching through the list of information?

#include <iostream>
#include <string>
using namespace std;
class Book

{
private:
string title;
int iD;
int year_pub;
string author;
public:
string getTitle();
int getId();
int getYear_Pub();
string getAuthor();
void set(string,int,int,string);
};
void Book::set(string title,int iD,int year_pub,string author)
{
this -> title = title;
this -> iD = iD;
this -> year_pub = year_pub;
this -> author = author;
}
string Book ::getTitle()
{
return title;
}
int Book ::getId()
{
return iD;
}
int Book ::getYear_Pub()
{
return year_pub;
}
string Book ::getAuthor()
{
return author;
}
int main()
{

Book A,B,C;
int pick, year;

A.set("C++ Plus Data Structures:5th Edition",101,2013,"Nell Dale");
B.set("Starting out with C++: From Control Structures through Objects",102,1996,"Tony Gaddis");
C.set("C++ How to Program",103,2007,"Paul and Harvey Deitel");

cout<< "Welcome to Book Search"<<endl;
do
    { 
        cout<<endl;
	    cout<<"Enter 1 to see all books."<<endl;
		cout<<"Enter 2 to search a book by the Year."<<endl;
		cout<<"Enter 3 to exit this program."<<endl;
		cout<<"Enter a number: "<<endl;
		cin >> pick;

		switch(pick)

		{
		case 1:
			cout<<endl;
			cout<<"There is 3 books here:"<<endl; 
			cout<<endl;
		    
			cout<<"Title:"<<A.getTitle()<<endl;
			cout<<"ID:"<<A.getId()<<endl;
			cout<<"Year:"<<A.getYear_Pub()<<endl;
			cout<<"Author:"<<A.getAuthor()<<endl;
			cout<<endl;
			
			cout<<"Title:"<<B.getTitle()<<endl;
			cout<<"ID:"<<B.getId()<<endl;
			cout<<"Year:"<<B.getYear_Pub()<<endl;
			cout<<"Author:"<<B.getAuthor()<<endl;
			cout<<endl;
           
			cout<<"Title:"<<C.getTitle()<<endl;
			cout<<"ID:"<<C.getId()<<endl;
			cout<<"Year:"<<C.getYear_Pub()<<endl;
			cout<<"Author:"<<C.getAuthor()<<endl;
			break;
	case 2:
			cout<<"Please enter the year you would like to search"<<endl;
			cin >>year;
				if (year==A.getYear_Pub())
		
					{
						cout<<"Title:"<<A.getTitle()<<endl;
					    cout<<"ID:"<<A.getId()<<endl;
	                    cout<<"Year:"<<A.getYear_Pub()<<endl;
		                cout<<"Author:"<<A.getAuthor()<<endl;
		                cout<<endl;
				   }

				else if (year==B.getYear_Pub())
				   {
						cout<<"Title:"<<B.getTitle()<<endl;
						cout<<"ID:"<<B.getId()<<endl;
			            cout<<"Year:"<<B.getYear_Pub()<<endl;
						cout<<"Author:"<<B.getAuthor()<<endl;
						cout<<endl;
                   }
				else if(year==C.getYear_Pub())
				  {
						cout<<"Title:"<<C.getTitle()<<endl;
						cout<<"ID:"<<C.getId()<<endl;
						cout<<"Year:"<<C.getYear_Pub()<<endl;
						cout<<"Author:"<<C.getAuthor()<<endl;
						cout<<endl;
                  }
				else
				cout<<"There is no book by that year."<<endl;

		break;
		case 3:
		cout<<"End of program."<<endl;

		break;
        default:
        cout<<"Not a valid number.\n"
        <<"Enter again."<<endl;
      }
}
while(pick !=3);

return 0;

}

[raghav.naganathan]

Here is a small hint for you.

You need to know that for a binary search to work correctly, the data needs to be a sorted array in ascending order.

regards,
Raghav

[amyceres]

raghav.naganathan, on 08 November 2012 - 11:23 PM, said:

Here is a small hint for you.

You need to know that for a binary search to work correctly, the data needs to be a sorted array in ascending order.

regards,
Raghav

would it be better if I have it in a linked list?

[raghav.naganathan]

I am no expert but I feel that an array is the simplest way of implementing a binary search.

regards,
Raghav

[Adak]

A binary search is a brilliant bit of simple logic. Say I asked you to guess the number I'm thinking of between 1 and 8. So the search space is 8 int's, and you, being clever, decided to use a binary search algorithm.

So you guess 4, cutting the space roughly into two halves (Binary = 2, btw).

I say 4 is too low.

You know there is no valid number below 5 now, the search space is 5,6,7,8, and you guess 7.

I say 7 is too high.

You know there no valid number below 5, and now there is no valid number higher than 6. The search space is 5 & 6. You guess 6.

I say 6 is too high, and now you guess 5 since it's the only possible number.

There was a range of 8 to search through, and you found the correct answer in only 3 guesses. Nice but the real power of binary search comes into play when you have a hundred items or more to be searched through. For 1024 items, the correct answer can be found in 8 guesses (although a program will probably use 9 since it makes the code faster).

Every time you double the size of the search space, the number of guesses increases by just 1 or 2, which is absolutely fantastic!

For example, I have a dictionary file of about 45,000 words. I want to find all the words in a novel, that aren't included in my small dictionary. For the novel, I chose "A Tale of Two Cities". Using a binary search, I checked all the words in this e-book, searching through my dictionary for every single word in Tale of Two Cities - yes, there were plenty of repeated words. But I don't care, because the whole search was done in less than 5 seconds! And I've got the list of words that were not in my dictionary.

You can use a binary search on any SORTED set of objects: integers, floats, doubles, strings, struct members, char's - anything! The objects just have to be in sorted order - that's it. It's much faster if you keep the objects in memory, (SSD's are like memory), and located locally, instead of on a mechanical or network drive.

This is a non-optimized version, from K&R:

int binsearch(int x, int v[], int n) {  //x is the target we're looking for in v[]
   int low, mid, high;
   low = 0;
   high = n-1; //n is the size of v[]   

   while(low <= high) {
      mid = (low+high)/2;
      if(x < v[mid])
         high = mid-1;
      else if(x > v[mid]
         low = mid+1;
      else
         return mid;   //target was found
   }
   return -1;       //target is not in v[]
}

Like sorting, it's easy to code up a binary search that doesn't work right, so keep a reference handy at first.

This is the help page from Pelles C's compiler and IDE, on bsearch():

Quote

Syntax:
typedef int (__cdecl *cmpfunc_t)(const void *elem1, const void *elem2); /* user-defined function prototype */

void * bsearch(const void *key, const void *base, size_t num, size_t size, cmpfunc_t funcptr);

Declared in:
<stdlib.h>

Description:
The bsearch function performs a binary search in a sorted array of num elements, where each element is size number of bytes. The argument base is a pointer to the array to be searched, and key is the value to search for.


The argument funcptr is a pointer to a user-defined function that compare two array elements and return their relationship. The user-defined function may be called repeated times by bsearch during the search. It will be passed the following arguments (in this order):

1) a pointer to the first element (elem1).

2) a pointer to the second element (elem2).

The user-defined function shall return an integer less than, equal to, or greater than zero if the first element is considered to be respectively less than, equal to, or greater than the second.

Returns:
A pointer to a matching element of the array, or a null pointer if no match is found. If two elements compare as equal, which element is matched is unspecified.

[amyceres]

Adak, on 09 November 2012 - 08:38 AM, said:

A binary search is a brilliant bit of simple logic. Say I asked you to guess the number I'm thinking of between 1 and 8. So the search space is 8 int's, and you, being clever, decided to use a binary search algorithm.

So you guess 4, cutting the space roughly into two halves (Binary = 2, btw).

I say 4 is too low.

You know there is no valid number below 5 now, the search space is 5,6,7,8, and you guess 7.

I say 7 is too high.

You know there no valid number below 5, and now there is no valid number higher than 6. The search space is 5 & 6. You guess 6.

I say 6 is too high, and now you guess 5 since it's the only possible number.

There was a range of 8 to search through, and you found the correct answer in only 3 guesses. Nice but the real power of binary search comes into play when you have a hundred items or more to be searched through. For 1024 items, the correct answer can be found in 8 guesses (although a program will probably use 9 since it makes the code faster).

Every time you double the size of the search space, the number of guesses increases by just 1 or 2, which is absolutely fantastic!

For example, I have a dictionary file of about 45,000 words. I want to find all the words in a novel, that aren't included in my small dictionary. For the novel, I chose "A Tale of Two Cities". Using a binary search, I checked all the words in this e-book, searching through my dictionary for every single word in Tale of Two Cities - yes, there were plenty of repeated words. But I don't care, because the whole search was done in less than 5 seconds! And I've got the list of words that were not in my dictionary.

You can use a binary search on any SORTED set of objects: integers, floats, doubles, strings, struct members, char's - anything! The objects just have to be in sorted order - that's it. It's much faster if you keep the objects in memory, (SSD's are like memory), and located locally, instead of on a mechanical or network drive.

This is a non-optimized version, from K&R:

int binsearch(int x, int v[], int n) {  //x is the target we're looking for in v[]
   int low, mid, high;
   low = 0;
   high = n-1; //n is the size of v[]   

   while(low <= high) {
      mid = (low+high)/2;
      if(x < v[mid])
         high = mid-1;
      else if(x > v[mid]
         low = mid+1;
      else
         return mid;   //target was found
   }
   return -1;       //target is not in v[]
}

Like sorting, it's easy to code up a binary search that doesn't work right, so keep a reference handy at first.

This is the help page from Pelles C's compiler and IDE, on bsearch():

Quote

Syntax:
typedef int (__cdecl *cmpfunc_t)(const void *elem1, const void *elem2); /* user-defined function prototype */

void * bsearch(const void *key, const void *base, size_t num, size_t size, cmpfunc_t funcptr);

Declared in:
<stdlib.h>

Description:
The bsearch function performs a binary search in a sorted array of num elements, where each element is size number of bytes. The argument base is a pointer to the array to be searched, and key is the value to search for.


The argument funcptr is a pointer to a user-defined function that compare two array elements and return their relationship. The user-defined function may be called repeated times by bsearch during the search. It will be passed the following arguments (in this order):

1) a pointer to the first element (elem1).

2) a pointer to the second element (elem2).

The user-defined function shall return an integer less than, equal to, or greater than zero if the first element is considered to be respectively less than, equal to, or greater than the second.

Returns:
A pointer to a matching element of the array, or a null pointer if no match is found. If two elements compare as equal, which element is matched is unspecified.

Thanks for the example now I need to use a linked list with a pointer and queue..