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 <[email protected]>wrote:
> Hi pharta :
> " find the point where it is rotated to get 14<->1 O(log(n)) " how can
> you find rotation point in log(n) ?
>
>
> On Fri, Jun 8, 2012 at 6:57 PM, partha sarathi Mohanty <
> [email protected]> wrote:
>
>> It is easy.. find the point where it is rotated to get 14<->1 O(log(n))
>> since 2<14 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 <[email protected]> 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 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] and
>>> a[k] < a[0]. Then if x < a[k], do a binary search to find x in {a[k] ...
>>> a[n-1]}; otherwise do a binary search to find x in {a[0] ... a[k]}.
>>>
>>> Dave
>>>
>>> On Friday, June 8, 2012 8:41:47 AM UTC-5, Hassan Monfared wrote:
>>>
>>>> A sorted array of integers is rotated unknown times. find an item in
>>>> O(logn) time and O(1) space complexity.
>>>> for example : 1,2,3,7,10,14 -------rotated 3 times------> 7,10,14,1,2,3
>>>> find 2 in O(logn) time in O(1) space complexity
>>>>
>>>> Regards
>>>> Hassan H. Monfared
>>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To view this discussion on the web visit
>>> https://groups.google.com/d/msg/algogeeks/-/KD9Hz01ZIJ8J.
>>>
>>> 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.
>>>
>>
>> --
>> 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.
>>
>
> --
> 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.
>
--
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.
