smthng like this...
*if*(arr[mid] arr[mid + 1])
return mid;
if(arr[low] arr[mid])
return findPoint(arr, low, mid-1);
else
return findPoint(arr, mid + 1, high);
On Sat, Jun 9, 2012 at 12:36 AM, Hassan Monfared hmonfa...@gmail.comwrote:
Hi pharta :
find the point where
@Hassan: This is not possible without additional conditions. E.g., you
cannot find the 1 in the array {0,0,0,...,0,1,0,0,...,0} in less than O(n)
time.
But with the condition that the elements of the array are pairwise
distinct, you can use a binary search to find k such that a[k-1] a[0]
Yes,
Thanks Dave. for non-distinct items It's not possible.
On Fri, Jun 8, 2012 at 6:44 PM, Dave dave_and_da...@juno.com wrote:
@Hassan: This is not possible without additional conditions. E.g., you
cannot find the 1 in the array {0,0,0,...,0,1,0,0,...,0} in less than O(n)
time.
But with
It is easy.. find the point where it is rotated to get 14-1 O(log(n))
since 214 that means u have to find it in subarray [123].. do a binary
search here o(long(n))
final 2*O(log(n))...
On Fri, Jun 8, 2012 at 7:44 PM, Dave dave_and_da...@juno.com wrote:
@Hassan: This is not possible without