find the distrotion first in the array using binary search . now you have the last element where the array was rotated. So pick your range, it will be either left or right subarray. Binary search in that. log(n).
On Sat, Jul 30, 2011 at 11:01 AM, Mohit Goel <mohitgoel291...@gmail.com>wrote: > Given a sorted array of n integers that has been > rotated an unknown number of > times, give an O(log n) algorithm that finds an element in the > array You may assume > that the array was originally sorted in increasing order > > EXAMPLE: > > Input: find 5 in array (15 16 19 20 25 1 3 4 5 7 10 14) > > Output: 8 (the index of 5 in the array) > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@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. > -- Ankur Khurana Computer Science Netaji Subhas Institute Of Technology Delhi. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@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.
