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.
def binary_search_rotated(arr, key):#TODO: Write - Your - Codereturn -1
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)))
The runtime complexity of this solution is logarithmic, $O(log n)$.
The memory complexity of this solution is constant, $O(1)$.
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 low
to 0 and high
to the length of the array minus one.
Enter a while
loop that continues while low
is less than or equal to high
.
Inside the loop, calculate mid
using the formula low + (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 to arr[mid]
, it implies that the left subarray (from low to mid) is sorted:
high
to mid - 1
. Otherwise, update the low
to mid + 1
.Otherwise, it’s obvious that arr[low]
is greater than arr[mid]
, which it indicates that the right subarray (from mid to high) is sorted:
target
falls within this range, update the low
to mid + 1
. Otherwise, update the high
to mid - 1
.If the target is not found after the loop, return -1
to 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!