Write a code to search in rotated sorted array.
Given a sorted array and a target value. Suppose this sorted array is rotated any number of times.
Write a code to search a target value in a sorted and rotated array. Return the index of a target value. If the target value is not found then return -1.
NOTE: The array only contains distinct values.
For example:
Input: {4, 5, 6, 7, -1, 0, 1, 2}, target = 0
Output: 5
In the above example, we have to search 0 in the rotated array. The element 0 is present at 5th index.
The array is rotated which makes this problem tricky. Our task is to solve this problem efficiently.
There are multiple approaches we can use to solve this problem. Also, I have explained all the approaches and their java code through the video tutorial. The link to that video tutorial is present at the end of this post.
Search Element in a Rotated Sorted Array using Linear Search
The easiest approach is to search the target value using linear search. Traverse an array and compare each array element with the target value. If an array element is equal to the target value then return its index, else return -1.
The time complexity of this approach is O(n) and its space complexity is O(1).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
//Search target value using linear search public static int searchTargetUsingLinearSearch(int[] arr, int target) { //If array is empty, return -1 if(arr.length == 0) { return -1; } //Traverse an array for(int i = 0; i < arr.length; i++) { //If element is found, then return it's index if(arr[i] == target) { return i; } } return -1; } |
It is the easiest way to approach this problem. Can we improve its time complexity? Is there any other approach we can use to solve this problem efficiently?
We can solve this problem in O(logn) time complexity using Binary Search.
Find first and last position of element in sorted array
Programming questions on binary search
Search in Rotated Sorted Array using Binary Search
We can use a binary search to solve this problem in O(logn) time complexity. How we can use binary search in a sorted and rotated array?
The interesting property of a sorted and rotated array is that when we divide the array into two halves. At least, one of the two halves is always sorted. If mid happens to the point of rotation then both the (right and left) halves will be sorted.
By using this observation we can use binary search to solve this problem. Here are the following steps.
i) In a binary search, we first calculate the mid. The next step is to compare the value present at the mid index to the target value. If both are equal then return the mid index.
ii) If the value present at the mid index is not equal to the target. Then compare the value present at mid index is greater than the value present at start index. If this is the case, It means the values present in this range are sorted. Then perform the following steps.
|
1 2 3 4 5 |
if(target >= arr[start] && target <= arr[mid]) { end = mid - 1; } else { start = mid+1; } |
iii) Else for arr[mid] to arr[end] perform following steps.
|
1 2 3 4 5 |
if(target >= arr[mid] && target <= arr[end]) { start = mid+1; } else { end = mid-1; } |
Let’s write its java code.
|
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 |
//Java code to Search in Rotated Sorted Array using binary search public class SearchInSortedRotated { public static int searchTarget(int[] arr, int target) { if(arr.length == 0) return -1; int start = 0; int end = arr.length - 1; while(start <= end) { int mid = (start + end)/2; //If target value is found if(arr[mid] == target) return mid; if (arr[start] <= arr[mid]) { if(target >= arr[start] && target <= arr[mid]) { end = mid - 1; } else { start = mid+1; } } else { if(target >= arr[mid] && target <= arr[end]) { start = mid+1; } else { end = mid-1; } } } return -1; } public static void main(String[] args) { int arr[] = {4,5,6,7,-1,0,1,2}; int target = 0; int result = searchTarget(arr, target); system.out.println(result); } } |
Search in Rotated Sorted Array LeetCode Solution
|
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 |
//Search in Rotated Sorted Array LeetCode Solution class Solution { public int search(int[] nums, int target) { if(nums.length == 0) { return -1; } int start = 0; int end = nums.length-1; while(start <= end) { int mid = (start + end)/2; if(nums[mid] == target) { return mid; } else if (nums[start] <= nums[mid]) { if(target >= nums[start] && target <= nums[mid]) { end = mid-1; } else { start = mid+1; } } else { if(target >= nums[mid] && target <= nums[end]) { start = mid+1; } else { end = mid-1; } } } return -1; } } |
Rotated Sorted Array Search InterviewBit Solution
A similar problem is present in Interviewbit.
|
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 |
//Rotated Sorted Array Search - Java Code public class Solution { public int search(final List<Integer> a, int b) { return searchResult(a, b, 0, a.size()-1); } public static int searchResult(List<Integer> a, int b, int start, int end) { if(start > end) { return -1; } int mid = (start + end)/2; if(a.get(mid) == b){ return mid; } if(a.get(start) <= a.get(mid)) { if(a.get(start) <= b && a.get(mid) >= b) { return searchResult(a, b, start, mid-1); } return searchResult(a, b, mid+1, end); } if(b >= a.get(mid) && b <= a.get(end)) { return searchResult(a, b, mid+1, end); } return searchResult(a, b, start, mid-1); } } |
