Jump to content

recursive find function for binary search


gate13

Recommended Posts

lost!

Well, I won't give you the full answer, since I am suspicious that this is homework. However, I will give you tips for it.

 

If you don't know what binary search is, it is the process of taking the middle element of an array, if it isn't equal to the key then find if the key is bigger or smaller than the selected element, either go left or right(assuming the list is sorted already). After that, select the middle element of the left or right side of the array.

 

This can easily be done recursively. Since you get an array as an input, simply find the middle element, do all the comparisons, and then create a new array that contains all the proper elements which will be inputed into the function again.

Link to comment
Share on other sites

If you don't know what binary search is, it is the process of taking the middle element of an array, if it isn't equal to the key then find if the key is bigger or smaller than the selected element, either go left or right(assuming the list is sorted already). After that, select the middle element of the left or right side of the array.

So far, so good.

 

This can easily be done recursively. Since you get an array as an input, simply find the middle element, do all the comparisons, and then create a new array that contains all the proper elements which will be inputed into the function again.

 

That would be the worst est implementation of binary search I heard of.

 

Making NEW ARRAY?

 

No.

 

That would be very slow implementation.

 

You should pass original array pointer, and indexes - to the beginning and to the end, or start index, and quantity (at the beginning start=0,quantity = list.length).

 

void binary_search( data *list, int start, int count, data x )

{

data value = list[ start + count / 2 ]; // take element at middle

if( x > value ) binary_search( list, start + count / 2, count / 2, x );

else if( x < value ) binary_search( list, start, count / 2, x );

else { /* found */ }

}

 

(I skipped actual finding code, it's just to give you picture of passing indexes, without creating new array!)

 

Link to comment
Share on other sites

So far, so good.

 

 

That would be the worst est implementation of binary search I heard of.

 

Making NEW ARRAY?

 

No.

 

That would be very slow implementation.

 

You should pass original array pointer, and indexes - to the beginning and to the end, or start index, and quantity (at the beginning start=0,quantity = list.length).

 

void binary_search( data *list, int start, int count, data x )

{

data value = list[ start + count / 2 ]; // take element at middle

if( x > value ) binary_search( list, start + count / 2, count / 2, x );

else if( x < value ) binary_search( list, start, count / 2, x );

else { /* found */ }

}

 

(I skipped actual finding code, it's just to give you picture of passing indexes, without creating new array!)

 

I apologize. I meant to say it that way.

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.