2010/12/5 juver++ <[email protected]>:
> Wrong.
> Counterexample: 1 2 2 2 2 6
suppose you mean 1 3 3 3 3 6?
1) divide-conquer
2) search binary, in each sub array [s, t],
mid = (s+t)/2
if t < array[mid]:
// no need to check the part after mid, all will fail
else if s > array[mid]:
// no need to check the part before mid, all will fail
// if we have the elements unique
if mid < array[mid]:
// no need to check the part after mid, all will fail
else if mid > array[mid]:
// no need to check the part before mid, all will fail
3) when the elements are unique, in [s, t],
if (array[s] = s && array[t] = t)
// all in [s, t] is ok
but I think its complexity will be O(n) in the worse case if elements
could be equal.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
