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.
