Quote:

> A sorted array of integers containing 20 elements, what is the maximum

> number of search tests that would be

> done, using a binary search techique on the array to find a particular

> element.

> am I right if I use this formular?? log2n

> if so, how to calculate??

Yep, you're right, and an outline of the proof goes something

like this:

let S(n) be the number of search tests needed to find an element

in a sorted list of n elements. Clearly S(1) =1

If you look at element n/2, three alternatives are possible:

- it's the element your're looking for;

- it's larger than the element you're looking for; or,

- it's smaller than the element you're looking for.

If the second or third alternative apply, check the appropriate

half of the list of elements. This yields:

S(n)= 1+S(n/2) -->

S(n)= 1+1+S(n/4) -->

S(n)= 1+1+ ... +1+S(1)= 2logn

does this clarify things a bit?

kind regards,