2010/12/5 juver++ <avpostni...@gmail.com>: > 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.