Search Rotated Array
Problem Statement
Search for a given number in a sorted array, with unique elements, that has been rotated by some arbitrary number. Return -1 if the number does not exist. Assume that the array does not contain duplicates.
Below is an original array before rotation
After performing rotation on this array 6 times it changes to:
The task is to find a given number in this array.
Hint
- Linear search is not an acceptable solution
- Try to solve the problem using binary search
Try it yourself
def binary_search_rotated(arr, key):#TODO: Write - Your - Codereturn -1
Solution
def binary_search_rotated(arr, key):low = 0high = len(arr) - 1while low <= high:mid = low + (high - low) // 2if arr[mid] == key:return midif arr[low] <= arr[mid]:if arr[low] <= key < arr[mid]:high = mid - 1else:low = mid + 1else:if arr[mid] < key <= arr[high]:low = mid + 1else:high = mid - 1return -1v1 = [6, 7, 1, 2, 3, 4, 5];print("Key(3) found at: " + str(binary_search_rotated(v1, 3)))print("Key(6) found at: " + str(binary_search_rotated(v1, 6)))v2 = [4, 5, 6, 1, 2, 3];print("Key(3) found at: " + str(binary_search_rotated(v2, 3)))print("Key(6) found at: " + str(binary_search_rotated(v2, 6)))
Solution Explanation
Runtime complexity
The runtime complexity of this solution is logarithmic, .
Memory complexity
The memory complexity of this solution is constant, .
Solution Breakdown
To tackle rotation in a binary search for a rotated array, we adjust the search range based on the middle element’s comparisons as follows:
-
If the element at the middle index matches the target, return the index of the middle element, as the target has been found.
-
If the element at the middle index is greater than or equal to the element at the start index, it implies that the left subarray (from the start to the middle) is sorted:
-
Now, check if the target falls within the range of elements from the leftmost element to the middle element. If it does, adjust the search range to focus on the left subarray.
-
Otherwise, adjust the search range to focus on the right subarray.
-
-
If the element at the middle index is less than the element at the end index, it indicates that the right subarray (from the middle to the end) is sorted:
-
Check if the target falls within the range of elements from the middle element to the rightmost element. If it does, adjust the search range to focus on the right subarray.
-
Otherwise, adjust the search range to focus on the left subarray.
-
To implement the algorithm:
-
Initialize
lowto 0 andhighto the length of the array minus one. -
Enter a
whileloop that continues whilelowis less than or equal tohigh.-
Inside the loop, calculate
midusing the formulalow + (high - low) // 2. -
Check if the element at the middle index matches the target. If it does, return the index of the middle element.
-
If
arr[low]is less than or equal toarr[mid], it implies that the left subarray (from low to mid) is sorted:- If the target falls within this range, update the
hightomid - 1. Otherwise, update thelowtomid + 1.
- If the target falls within this range, update the
-
Otherwise, it’s obvious that
arr[low]is greater thanarr[mid], which it indicates that the right subarray (from mid to high) is sorted:- If the
targetfalls within this range, update thelowtomid + 1. Otherwise, update thehightomid - 1.
- If the
-
If the target is not found after the loop, return
-1to indicate its absence in the array.
-
Practice problems like this and many more by checking out our Grokking the Coding Interview: Patterns for Coding Questions course!
