Check whether the first element in the array is greater than the last element in the array. If it is true, it means the array is rotated after sorting.
Now, take the middle element of the array and check whether it is greater than the last element of the array. If true, it means the first half of the array is in sorted ascending order while the second half of the array is the place where the biggest and smallest elements of the array are present. If false, it means the second half of the array is in sorted ascending order while the first half of the array is the place where the biggest and smallest elements of the array are present. Check whether k falls between the sorted ascending half of the array. If yes, it is pretty simple Browse thru all elements or do a binary search within this sub array. If it falls in the sorted largest-to-smallest-containing half of the array, consider this half as your new array and proceed the same steps as above to find out the integer value k. Eg: Following numbers are in ascending order as their indices with k falling between n1 and n2 Index - 0 1 2 3 4 5 6 7 8 Value - n5, n6, n7, n0, n1,k,n2,n3, n4 According to the above method, 1. Check whether the first element is greater than the last element -- True. So, the array is rotated after sorting 2. Check whether the middle element(n1) is greater than the first element(n5) - False. So, the second half of the array [4-8] are sorted while indices [0-3] are sorted but not ascending. 3. Check whether k lies in between the second half. -- True k > n1 and k < n4. 4. Do a binary search between indices 4- 8 to get the element k. Index - 0 1 2 3 4 5 6 7 8 Value - n6, k, n7, n0, n1, n2,n3,n4, n5 On having the above example where the steps 1 & 2 still hold true 3.Check whether k lies in between the second half of the array [4-8] -- False. So, it falls in the first half of the array. 4. Assume sub array [0-4] as a new array and proceed with step 1. When you just have 3 elements left out (when k is the largest or smallest element), you can do a manual comparison and find k On Tue, Jun 8, 2010 at 7:41 AM, Rohit Saraf <rohit.kumar.sa...@gmail.com>wrote: > You can do binary search for the largest element in log n trivially. > And then you know the shift ! > > -- > -------------------------------------------------- > Rohit Saraf > Second Year Undergraduate, > Dept. of Computer Science and Engineering > IIT Bombay > http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> > > -- > 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<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- Luv, S.Antony Vincent Pandian -- 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.
