4 Replies - 4288 Views - Last Post: 03 December 2008 - 02:38 PM Rate Topic: -----

#1 emeighty  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 9
  • Joined: 01-July 08

Finding the largest number in a Binary search

Post icon  Posted 29 July 2008 - 04:23 AM

I am having a lot of trouble finding the largest number in a binary search using recursion. The book gives me some basic code on how to search on, but not how to find the largest number in one. The question asks me to implement this a helper function but to start, I just want to get the inner workings down.

Say that i had an array of {1,6,8,3} and i had to use recursion to find the largest number in it.


this is the example that was given to search for an value in the array that was already given.


#include<iostream>
using namespace std;

int binarySearch(const int anArray[], int first, int last, int value)
{
	int index;
	if (first >last )
	index =-1;
	
	else 
	{ //invariant : If value is in AnArray,
	  //			anArray[first] <= value <= anArray[last]
	  
	  int mid = (first + last)/2;
	  
	 if ( value==anArray[mid])
	 index = mid; //value found at mid;
	 
	 else if (value <anArray[mid])
	 // point x
	 index = binarySearch(anArray, first, mid-1, value);
	 // keep in mind that mid-1 become the "last" in the next recursive call
	 
	 else
	 //point y
	 index = binarySearch(anArray, mid+1, last, value );
	 // keep in mind that "mid+1" will be first in the next recursive call
	 // as in (first+last)/2, the value at mid+1 is now firsts.
	
	
	 } // end if
		 return index;
	 
	 }//end binarySearch
		 
	 int main()
	 
	 {
		 int first=0;
		 int last=7;
		 int value=29;
		 
		 int anArray1[]={1,5,9,12,15,21,29,31};
		 
		 binarySearch(anArray1, first, last, value);
				  //cout << value << endl;
		 
		 
		 system("pause");
		 return 0;
		 }
		 
		 
	  


the book gives
this as in what it wants in the example.

if( anArray has only 1 item)
maxArray(anArray) is the item in the array

else if (anArray has more than 1 item)
maxArray(anArray) is the maximum of
maxArray(left half of anArray) and
maxArray(right half of anArray)


any suggestions?

Is This A Good Question/Topic? 0
  • +

Replies To: Finding the largest number in a Binary search

#2 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2256
  • View blog
  • Posts: 9,444
  • Joined: 29-May 08

Re: Finding the largest number in a Binary search

Posted 29 July 2008 - 04:35 AM

To do a binary search the list needs to sorted first.
Plus if you're looking for the largest value it is the highest element.

I think you need to look at QuickFind, which can find the Nth Item without sorting.
QuickFind
Was This Post Helpful? 0
  • +
  • -

#3 emeighty  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 9
  • Joined: 01-July 08

Re: Finding the largest number in a Binary search

Posted 29 July 2008 - 05:02 AM

View PostAdamSpeight2008, on 29 Jul, 2008 - 04:35 AM, said:

To do a binary search the list needs to sorted first.
Plus if you're looking for the largest value it is the highest element.

I think you need to look at QuickFind, which can find the Nth Item without sorting.
QuickFind



Quickfind looks a little too much for my level
Was This Post Helpful? 0
  • +
  • -

#4 emeighty  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 9
  • Joined: 01-July 08

Re: Finding the largest number in a Binary search

Posted 29 July 2008 - 06:34 AM

just a few random questions.
do any of u spend days on one problem with homework and still get nowhere?

did you learn online or in a classroom? I am learning online and it just seems as tho , they dont take baby steps to get the foundation right, sort of just throw u into the fire and grasp a thin rope to try to get out. I bought 3 books to try to get an understanding of topics the crappy textbook doesnt give examples of "How to" It's problably just me, but a simple "this is how you do this ,and here is 5 example of how its done" then things would be much simpler.

Sorry, just had to vent some frustration.
Was This Post Helpful? 0
  • +
  • -

#5 mor_eli  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 03-December 08

Re: Finding the largest number in a Binary search

Posted 03 December 2008 - 02:38 PM

Hey,

did you figure out how to program this function? For the life of me I can't get this figured out since I don't understand what's the base condition...

Any tips are greatly appreciated!!!
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1