recursive find function for binary search

[gate13]

lost!

Edited March 14, 2015 by gate13

[Unity+]

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.

[Sensei]

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!)

 

[Unity+]

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.