Search an element in a circularly sorted array
Given a circularly sorted integer array, search an element in it. Assume there are no duplicates in the array, and the rotation is in the anti-clockwise direction.
For example,
nums = [8, 9, 10, 2, 5, 6]
target = 10
Output: Element found at index 2
Input:
nums = [9, 10, 2, 5, 6, 8]
target = 5
Output: Element found at index 3
Related Posts:
A simple solution would be to run a linear search on the array and find the given element’s index. The problem with this approach is that its worst-case time complexity is O(n), where n is the size of the input. This solution also does not take advantage of the fact that the input is circularly sorted.
We can easily solve this problem in O(log(n)) time by modifying the binary search algorithm. We know that the middle element always divides the array into two subarrays, and the target element can lie only in one of these subarrays. It is worth noticing that at least one of these subarrays will always be sorted. If the middle element happens to be the point of rotation (minimum element), then both left and right subarrays will be sorted, but in any case, one half (subarray) must be sorted. The idea is to use this property to discard the left half or the right half at each iteration of the binary search.
The algorithm can be implemented as follows in C, Java, and Python:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
#include <stdio.h> // Function to find an element `target` in a circularly sorted array int searchCircularArray(int nums[], int n, int target) { // search space is nums[low…high] int low = 0, high = n - 1; // loop till the search space is exhausted while (low <= high) { // find the mid-value in the search space and // compares it with the target int mid = (low + high)/2; // if the target is found, return its index if (target == nums[mid]) { return mid; } // if right half nums[mid…high] is sorted and `mid` is not // the target element if (nums[mid] <= nums[high]) { // compare target with nums[mid] and nums[high]to know // if it lies in nums[mid…high] or not if (target > nums[mid] && target <= nums[high]) { low = mid + 1; // go searching in the right sorted half } else { high = mid - 1; // go searching left } } // if left half nums[low…mid] is sorted, and `mid` is not // the target element else { // compare target with nums[low] and nums[mid] to know // if it lies in nums[low…mid] or not if (target >= nums[low] && target < nums[mid]) { high = mid - 1; // go searching in the left sorted half } else { low = mid + 1; // go searching right } } } // target not found or invalid input return -1; } int main(void) { int nums[] = {9, 10, 2, 5, 6, 8}; int target = 5; int n = sizeof(nums)/sizeof(nums[0]); int index = searchCircularArray(nums, n, target); if (index != -1) { printf("Element found at index %d", index); } else { printf("Element not found in the array"); } return 0; } |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
class Main { // Function to find an element in a circularly sorted array public static int searchCircularArray(int[] nums, int target) { // search space is nums[left…right] int left = 0; int right = nums.length - 1; // loop till the search space is exhausted while (left <= right) { // find the mid-value in the search space and // compares it with the target int mid = (left + right) / 2; // if the key is found, return its index if (target == nums[mid]) { return mid; } // if right half nums[mid…right] is sorted and `mid` is not // the key element if (nums[mid] <= nums[right]) { // compare key with nums[mid] and nums[right] to know // if it lies in nums[mid…right] or not if (target > nums[mid] && target <= nums[right]) { // go searching in the right sorted half left = mid + 1; } else { right = mid - 1; // go searching left } } // if left half nums[left…mid] is sorted, and `mid` is not // the key element else { // compare key with nums[left] and nums[mid] to know // if it lies in nums[left…mid] or not if (target >= nums[left] && target < nums[mid]) { // go searching in the left sorted half right = mid - 1; } else { left = mid + 1; // go searching right } } } // key not found or invalid input return -1; } public static void main(String[] args) { int[] nums = {9, 10, 2, 5, 6, 8}; int key = 5; int index = searchCircularArray(nums, key); if (index != -1) { System.out.println("Element found at index " + index); } else { System.out.println("Element not found in the array"); } } } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
# Function to find an element in a circularly sorted list def searchCircularList(nums, target): # search space is nums[left…right] (left, right) = (0, len(nums) - 1) # loop till the search space is exhausted while left <= right: # find the mid-value in the search space and # compares it with the target mid = (left + right) // 2 # if the key is found, return its index if target == nums[mid]: return mid # if right half nums[mid…right] is sorted and `mid` is not # the key element if nums[mid] <= nums[right]: # compare key with nums[mid] and nums[right] to know # if it lies in nums[mid…right] or not if nums[mid] < target <= nums[right]: left = mid + 1 # go searching in the right sorted half else: right = mid - 1 # go searching left # if left half nums[left…mid] is sorted, and `mid` is not # the key element else: # compare key with nums[left] and nums[mid] to know # if it lies in nums[left…mid] or not if nums[left] <= target < nums[mid]: right = mid - 1 # go searching in the left sorted half else: left = mid + 1 # go searching right # key not found or invalid input return -1 if __name__ == '__main__': nums = [9, 10, 2, 5, 6, 8] key = 5 index = searchCircularList(nums, key) if index != -1: print('Element found at index', index) else: print('Element found not in the list') |
Output:
Element found at index 3
The time complexity of the above solution is O(log(n)) and doesn’t require any extra space.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)