0 0 votes You are given a sorted array of $n$ elements that has been rotated an unknown number of times $($e.g., $\verb|[4,5,6,7,0,1,2]|)$. You need to find a target element in this array. What is the most efficient worst-case time complexity to achieve this?$O(1)$ $O(\log n)$ $O(\sqrt{n})$ $O(n)$ Programming in Python goclasses python-&-dsa goclasses-da-dpp goclasses-da-dpp-day-89 goclasses-python-&-dsa-practice-questions + – GO Classes 166 views answer comment Share Follow Print 0 reply Please log in or register to add a comment.
0 0 votes Modified Binary Search: Even though the array is rotated, it still consists of two sorted subarrays.Logic: In each step of the binary search, at least one half $($either $\verb|left|$ to $\verb|mid|$ or $\verb|mid|$ to $\verb|right|)$ must be sorted.Execution: By checking which half is sorted and whether the target lies within that sorted range, we can discard half of the search space in each iteration.Complexity: Since we reduce the search space by half each time, the complexity remains $O(\log n)$, identical to standard Binary Search. GO Classes answered Jan 20 GO Classes comment Share Follow 0 reply Please log in or register to add a comment.
