Problem: Sorted-Rotated Array Search(no duplication).
1 min readJan 23, 2019
Hints:
Finding an element in the array (unsorted n-element) requires a time complexity of n.
Finding an element in the array (sorted n-element) using binary search requires time complexity of log n.
Problem Statement: Search in Rotated Sorted Array
We can solve the problem by splitting into two sub-problem.
- Find the pivot element (starting element of the ascending) using the modified version of binary search. — time complexity (log n)
- Using the pivot element, finalize the range and do a binary search over it. — time complexity (log n)
overall time complexity:
log n + log n = 2 log n — > O(log n)
If you have feedback and suggestion feel free to give your comments.
