Snake???..Bond???

[Zero Tolerance]

hey guys....I feel robbed by my Structured fessor from last semester.....because I dont think we covered enough material to be in OOP...but Im in OOP now and gotta make the grade

anyway....very much like the code you guys helped me with....I found a binary search function that basically does the same

could either of you, or anyone else for that matter....help write a main function to run this function?

here it is

#include <iostream>

using namespace std;


int binarySearch(const int anArray[], int first, int last, int value)

//--------------------------------------------------------------------------------
// Searches the array items anArray[first] through
// anArray[last] for value by using a binary search.
// Precondition: 0<=first, last <= SIZE-1, where
// SIZE is the maximum size of the array, and
// anArray[first] <= anArray[first+1] <= ... <=
// anArray[last].
// Postcondition: If value is in the array, the function
// returns the index of the array item that equals value;
// otherwise the function returns -1.
//--------------------------------------------------------------------------------

{
int (first > last)
index = -1; // value not in original array

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 anArray[mid]

else if (value < anArray[mid]
// point X
index = binarySearch (anArray, first, mid-1, value);

else
//point Y
index = binarySearch(anArray, mid+1, last, value);
} // end else
return index;
} // end binarySearch


Im just unclear on how to utilize this function in a simple program...I do know that I need to call the function in the "main" function....just really am confused as to why and how

thanks in advance for any advice or help with getting me to understand this a lil better

might also be nice if someone could give some tips on structures in this forum.....maybe ill learn something that wasnt taught last semester cuz the teach didnt take it seriously enough....and now im finding it hard to keep up in OOP

thanks again!

[Anaconda]

Well firstly there is nothing object oriented about this code here, it is a standard procedural C function.

Unlike your last question, this function searches for a given number in a list of numbers. Instead of simply finding the maximum value in the list.

This type of search can greatly benefit from a specialized search, provided that the data is in a pre-arranged form. In this case an binary search and the list must be organiized with the values SORTED in ascending order.

What this function does is take the sorted array of values. It then uses the fact that the array is sorted to speed up finding if a given value is in the array. It performs this by testing the value of the element that exists in the middle of the range of the list, passed to it in first & last, against the desired value. If it matches, it simply returns the index where the match occured. If it fails it uses the fact that the list is sorted to decide if the value will be on the left or the right of the current position. It then recurses (calls itself) again, with the same search value, except this time with a reduced range. This reduced range is effectively half of the previous range. It will keep dividing down until it can no longer divide the list in two, if still no match has been found it will return -1.

This constant dividing down will yeld an answer very quickly. Actually since we're always dividing by 2, the answer will come in a number of tests (or less) equavalent to the number of bits needed to define the size of the list plus 1. So for a list of 10 numbers it should take no more than 4 guesses to find the correct value. For a list of 250 values should take 8 or less guesses. Just like in binary, the size of the list needs to double before another guess is needed to acheive the answer. Compare this to a linear search, the 250 element array, would require up to 250 comparisons to get the same answer.

As for using it, you call it like any other C function. You would pass it, the list (sorted) , zero as first, and the size of the array-1 as last, and finally the value you are lookiing for.


void main(void) {
int idx;
int myArray[] = {1,3,6,8,12,25,67,99};

// first let's run a search for a number we know does not exist
if((idx=binarySearch(myArray,0,7,33))==-1) {
printf("value 33 not found in myArray\n");
} else {
printf("value 33 found in myArray at index %d\n",idx);
}

// now let's run the search again, this time for a value that does exist
if((idx=binarySearch(myArray,0,7,67))==-1) {
printf("value 67 not found in myArray\n");
} else {
printf("value 67 found in myArray at index %d\n",idx);
}
}


The binary search function,you provided, would traverse the example list of numbers like the following tree. As you can see the worst case scenario would be 4 comparisons.


8
/ \
/ \
/ \
3 25
/ \ / \
1 6 12 67
\
99


Hopefully I've answered all your questions here. But it sounds to me like you need to take a step back, and review your fundamentaals, or you are going to have a real tough time keeping up with this course.

[Zero Tolerance]

yes...that makes sense to me and i appreciate you taking the time to break it down a lil further

the book we are using for OOP isnt as detailed in explaining this and it wouldnt matter that much IF we would of covered more material in Strucutred last semester....the only thing we covered in structured was basic about 4-5 different header files....simple arrays.....loops such as if/else, for, do/while...and barely got into writing our own functions....

i dont feel that the class challenged us enough to prepare us for this textbook this semester because the material assumes that we learned more than we did in structured

i think the best case scenerio for me is to buy another reference book that puts everything in order but doesnt draw it out too much to where i have to skip thru allot of it to find the information im looking for....any suggestions???

anyway...thanks again for the good explanation....you've been a great help!

oh yeah....i didnt mean to infer that this was an object question...its just an example of the binary search function in the text the school is using to teach OOP....

lata!

[Anaconda]

The OOP comment I made at the top, was just because many people panic, when learning programming, and they think it's OO code, thinking that it's going to be really hard and obscure. I just wanted to remove that, by indicating that this was just regular procedural code here.

As for books, there are tonnes of good ones out there. The book we used back when I took CS in university, was "C: A Software Engineering Approach" by Peter Darnell, and Phillip Margolis [ISBN: 0387946756], I still use it today, every now and again, when I forget something ;). I Highly recommend this book, few computer books I have have been as useful for as long. The book is still in print (new edition actually) but is relatively expensive (around $55). You might be able to find a used copy kicking around for less though.

http://www.amazon.com/exec/obidos/tg/detail/-/0387946756/qid=1064331233/sr=1-1/ref=sr_1_1/103-7984598-0358242?v=glance&s=books#product-details

[Zero Tolerance]

cool...ill see if i can get me a copy.....im still waiting to hear back from a job interview i had this past friday as a MS Instructor...at the time im on a very low budget of expenditures!

the 2 books i have right now is "Programming & Problem Solving with C++" by Nell Dale, Chip Weens, and Mark Headington (which was what we used for structured)....and "Data Abstraction & Problem Solving with C++" by Frank M. Carrano & Janet J. Prichard (text we are using for OOP)

also to add....the later book doesnt really even get into defining an "object" until the 3rd chapter....first 2 chapters are basically overviews of what we SHOULD have had a good grasp on in structured.....unfortunatly i feel that we didnt get in deep enough with it.....afterall i made an A in that class and never had to ask for help at all....but we just brushed the surface of a few things...

anyway....I think I need to get a tutor that is at least in Data Structures now....so I can get a lil better grasp on the fundamentals.....syntax isnt much of a problem....but implementation is....(for me)

again...thanks for all of your input....glad i have someone to ask these questions to and not get a stupid answer in return!

sssssssssBANG!

[Greg]

Originally posted by Zero Tolerance

again...thanks for all of your input....glad i have someone to ask these questions to and not get a stupid answer in return!

sssssssssBANG!

We save those questions for you. ;)

[woods26]

Boy that conda sure knows his sh#$ eh? heheh. OOP=Object oriented Poo