8 Replies - 2471 Views - Last Post: 24 September 2011 - 11:35 AM Rate Topic: -----

#1 javarookie1985  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 18
  • Joined: 12-May 11

Binary search of sorted array

Posted 24 September 2011 - 05:28 AM

Hi,

I need help for my binary search of Book list based on sorted book array result. I am still new in this field, my Bubble sort is working fine, but I got stuck at Binary Search, my program cannot find the appropriate book ID from the Sorted List for displaying output related to book ID. I really appreciate your advices.


void Swap(TYPE &first, TYPE &last)
{
	TYPE temp;
	temp = first;
	first = last;
	last = temp;
}



void BubbleSort(Book *array[], int size)
{	
	int smallest;
	for(int first = 0; first < size - 1; first++)
	{
		smallest = first;
		for(int current = smallest + 1; current < size; current++)
		{
			if(*array[current] < *array[smallest])
				smallest = current;
		}
		Swap(array[first],array[smallest]);
	}
}



bool BinarySeach(Book *array[], int size, unsigned int bookID, Book *sortedOutput)
{
	int first = 0;
	int last = size - 1;
	int middle;
	int position = -1;
 
	while(first <= last)
	{
		middle = (first + last)/2;
	        
                if(array[middle] == sortedOutput)
	        {
 		   position = middle;
   		   return (true);
                }
		else if(array[middle] > sortedOutput)
		{
		  last = middle - 1;
		}
		else
		{
		  first = middle + 1;
		}
	}
	return (false);
}



main program output

//sortedOutput(bookID,Bookname);
List of sorted Book 
101 - Dummy Adobe Photoshop
102 - HTML,CSS
103 - Visual Studio 2008
 
Please enter ID to search: 102
ID not found, please try again


I think my problem is in void BinarySearch(..), but I still haven't figure out the way to solve it. Please help !
Thank you

Is This A Good Question/Topic? 0
  • +

Replies To: Binary search of sorted array

#2 CTphpnwb  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2914
  • View blog
  • Posts: 10,092
  • Joined: 08-August 08

Re: Binary search of sorted array

Posted 24 September 2011 - 07:30 AM

It looks to me like you're passing an array of pointers when you want to pass an array.
Was This Post Helpful? 0
  • +
  • -

#3 javarookie1985  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 18
  • Joined: 12-May 11

Re: Binary search of sorted array

Posted 24 September 2011 - 07:51 AM

View PostCTphpnwb, on 24 September 2011 - 07:30 AM, said:

It looks to me like you're passing an array of pointers when you want to pass an array.


Thanks for the reply. Would you please explain more specific about it ? Thanks
Was This Post Helpful? 0
  • +
  • -

#4 CTphpnwb  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2914
  • View blog
  • Posts: 10,092
  • Joined: 08-August 08

Re: Binary search of sorted array

Posted 24 September 2011 - 08:07 AM

Arrays decay to pointers when passed to functions. Declaring Book *array[] is saying you want to pass an array of pointers and I don't think that's what you want.
Was This Post Helpful? 0
  • +
  • -

#5 javarookie1985  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 18
  • Joined: 12-May 11

Re: Binary search of sorted array

Posted 24 September 2011 - 08:32 AM

View PostCTphpnwb, on 24 September 2011 - 08:07 AM, said:

Arrays decay to pointers when passed to functions. Declaring Book *array[] is saying you want to pass an array of pointers and I don't think that's what you want.


Hi,
For the BinarySearch declarations, I have to target the book record in the array of Books after it sorted using Buble Sort. You can see the output of the program, it displays all the books from sorted Arrays and then I search the the book by Book ID (e.g. 102), but I still get error (not found the item), so I think I haven't located properly.

bool BinarySeach(Book *array[], int size, unsigned int bookID, Book *sortedOutput)

I also provide the code for main(), so you can see closer what I am doing
int main()
{
	Book *sortarray[Array_Size];

	for(int i = 0 ; i < Array_Size ; i++)
		sortarray[i] = &(data[i]);

	BubbleSort(sortarray, Array_Size);

	for(int i = 0 ; i < Array_Size ; i++)
		cout << *(sortarray[i]) << endl;

	unsigned int inputBookId;
	
	Book sortedOutput(0,"");
	
	cout << endl << "Please enter ID to search: ";
	cin >> inputBookId;
	while(inputBookId != 0)
	{
		if(BinarySeach(sortarray, Array_Size, inputBookId, &sortedOutput))
			cout << sortedOutput << endl;
		else
			cout << "ID not found, please try again" << endl;

		Book sortedOutput(0, "");
		cout << endl << "Please enter ID to search: ";
		cin >> inputBookId;
	}

	return 0;
}



Thank you

This post has been edited by javarookie1985: 24 September 2011 - 08:36 AM

Was This Post Helpful? 0
  • +
  • -

#6 CTphpnwb  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2914
  • View blog
  • Posts: 10,092
  • Joined: 08-August 08

Re: Binary search of sorted array

Posted 24 September 2011 - 08:53 AM

Maybe this will make it clearer. I duplicate your way using integer as the type instead of Book, and then do it without pointers. See what gets the error?

Attached image(s)

  • Attached Image

Was This Post Helpful? 0
  • +
  • -

#7 javarookie1985  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 18
  • Joined: 12-May 11

Re: Binary search of sorted array

Posted 24 September 2011 - 09:45 AM

View PostCTphpnwb, on 24 September 2011 - 08:53 AM, said:

Maybe this will make it clearer. I duplicate your way using integer as the type instead of Book, and then do it without pointers. See what gets the error?


Thanks you for your advices. In this case, I must use the pointer for declaring Bubble Sort, but I believe my BubbleSort is not the problem, as it is still sorting properly. You can find the attached my full program, it is still sorting good, but when I try to search the specific Book ID, it returns false. That is the issue of Binary Search I want to solve.

Thank you

Attached File(s)


This post has been edited by javarookie1985: 24 September 2011 - 09:46 AM

Was This Post Helpful? 0
  • +
  • -

#8 CTphpnwb  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2914
  • View blog
  • Posts: 10,092
  • Joined: 08-August 08

Re: Binary search of sorted array

Posted 24 September 2011 - 11:25 AM

Well, I guess you want something like this:
#include <iostream>

#include "ProvidedData.h"

using namespace std;

template<class TYPE>

void Swap(TYPE &left, TYPE &right)
{
	TYPE temp;
	temp = left;
	left = right;
	right = temp;
}

bool BinarySearch(Book *array[], int size, unsigned int bookID, Book *sortedOutput)
{
	int first = 0;
	int last = size - 1;
	int middle;
	int position = -1;
//	cout << "testing "<< array[0]->GetBookID() << " bookID: " << bookID << endl;
	while(first <= last)
	{
		middle = (first + last)/2;
	        
        if(array[middle]->GetBookID() == bookID)
	    {
 		   position = middle;
				sortedOutput->SetBookID(middle);
				sortedOutput->SetTitleName(array[middle]->GetTitleName());
				sortedOutput->SetAuthorName(array[middle]->GetAuthorName());
   		   return (true);
        }
		else if(array[middle]->GetBookID() > bookID)
		{
		  last = middle - 1;
		}
		else
		{
		  first = middle + 1;
		}
	}
	return (false);
}

void BubbleSort(Book *array[], int size)
{	
	int smallest;
	for(int first = 0; first < size - 1; first++)
	{
		smallest = first;
		for(int current = smallest + 1; current < size; current++)
		{
			if(*array[current] < *array[smallest])
				smallest = current;
		}
		Swap(array[first],array[smallest]);
	}
}

int main(int argc, char *argv[])
{
	Book *sortArray[PROVIDED_DATA_SIZE];

	for(int i = 0 ; i < PROVIDED_DATA_SIZE ; i++)
		sortArray[i] = &(PROVIDED_DATA[i]);

	BubbleSort(sortArray, PROVIDED_DATA_SIZE);

	for(int i = 0 ; i < PROVIDED_DATA_SIZE ; i++)
		cout << *(sortArray[i]) << endl;

	unsigned int inputBookID;
	
	Book sortedOutput(0, "", "");
	
	cout << endl << "Please enter a book ID to search";
	cin >> inputBookID;
	while(inputBookID != 0)
	{
		if(BinarySearch(sortArray, PROVIDED_DATA_SIZE, inputBookID, &sortedOutput))
			cout <<"BookID: " << sortedOutput.GetBookID() << " Title: "<< sortedOutput.GetTitleName() << " Author: " << sortedOutput.GetAuthorName() << endl;
		else
			cout << "Cannot find the item" << endl;

		Book output(0, "", "");
		cout << endl << "Please enter a Book ID to search: ";
		cin >> inputBookID;
	}

	return 0;
}


Was This Post Helpful? 0
  • +
  • -

#9 javarookie1985  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 18
  • Joined: 12-May 11

Re: Binary search of sorted array

Posted 24 September 2011 - 11:35 AM

View PostCTphpnwb, on 24 September 2011 - 11:25 AM, said:

Well, I guess you want something like this:
#include <iostream>

#include "ProvidedData.h"

using namespace std;

template<class TYPE>

void Swap(TYPE &left, TYPE &right)
{
	TYPE temp;
	temp = left;
	left = right;
	right = temp;
}

bool BinarySearch(Book *array[], int size, unsigned int bookID, Book *sortedOutput)
{
	int first = 0;
	int last = size - 1;
	int middle;
	int position = -1;
//	cout << "testing "<< array[0]->GetBookID() << " bookID: " << bookID << endl;
	while(first <= last)
	{
		middle = (first + last)/2;
	        
        if(array[middle]->GetBookID() == bookID)
	    {
 		   position = middle;
				sortedOutput->SetBookID(middle);
				sortedOutput->SetTitleName(array[middle]->GetTitleName());
				sortedOutput->SetAuthorName(array[middle]->GetAuthorName());
   		   return (true);
        }
		else if(array[middle]->GetBookID() > bookID)
		{
		  last = middle - 1;
		}
		else
		{
		  first = middle + 1;
		}
	}
	return (false);
}

void BubbleSort(Book *array[], int size)
{	
	int smallest;
	for(int first = 0; first < size - 1; first++)
	{
		smallest = first;
		for(int current = smallest + 1; current < size; current++)
		{
			if(*array[current] < *array[smallest])
				smallest = current;
		}
		Swap(array[first],array[smallest]);
	}
}

int main(int argc, char *argv[])
{
	Book *sortArray[PROVIDED_DATA_SIZE];

	for(int i = 0 ; i < PROVIDED_DATA_SIZE ; i++)
		sortArray[i] = &(PROVIDED_DATA[i]);

	BubbleSort(sortArray, PROVIDED_DATA_SIZE);

	for(int i = 0 ; i < PROVIDED_DATA_SIZE ; i++)
		cout << *(sortArray[i]) << endl;

	unsigned int inputBookID;
	
	Book sortedOutput(0, "", "");
	
	cout << endl << "Please enter a book ID to search";
	cin >> inputBookID;
	while(inputBookID != 0)
	{
		if(BinarySearch(sortArray, PROVIDED_DATA_SIZE, inputBookID, &sortedOutput))
			cout <<"BookID: " << sortedOutput.GetBookID() << " Title: "<< sortedOutput.GetTitleName() << " Author: " << sortedOutput.GetAuthorName() << endl;
		else
			cout << "Cannot find the item" << endl;

		Book output(0, "", "");
		cout << endl << "Please enter a Book ID to search: ";
		cin >> inputBookID;
	}

	return 0;
}



That is what I want to do. Thank you very much for helping me. Excellent help.

This post has been edited by javarookie1985: 24 September 2011 - 11:35 AM

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1