oh common shashank...its not that easy u told..... just do coding....then u will find the error in ur logic
On Fri, Aug 12, 2011 at 6:25 PM, WgpShashank <shashank7andr...@gmail.com>wrote: > Hi Guys Here is the algorithm for doing same in O(logn) > > Hint : Find the pivot point, divide the array in two sub-arrays and call > binary search. Thats It :) > > Algorithm > 1. A Pivot Point is point around which array is rotated so 1st we need to > find out its location/index. lets say it pivot. > a. to find pivot point we use same idea of binary search & check if > arr[mid]>a[mid+1] if true then return pivot=mid. > b else if arr[low]<a[mid] search for pivot in left > c. else search for pivot in right half of array. > Time Complexity O(logn) > > 2. Once we have found index of pivot point check if desired element is > same value at pivot index or not e.g. > a. ( if a[pivot]==value we are searching for ) the simply return true > or 1 . > Now call binary search for one of the two sub-arrays. > (ab) *If *element is greater than 0th element then search in > left array > (ac) *Else* Search in right array * > (ad) If *element is found in selected sub-array then return > index > *Else *return -1. > > Again Time Complexity O(logn) > > Hope You Can Make it in Running Code , Do Noify me if You Need More > Explanation or if missed Something?? > > *Regards > Shashank Mani "Computer Science Is Awesome So Why I Write Code" > Computer Science > Birla institute of Technology Mesra > * > > > > -- > 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/-/QPCzNLNf_sEJ. > > 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. > -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- 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.
