Yes,
Thanks Dave. for non-distinct items It's not possible.
On Fri, Jun 8, 2012 at 6: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.
