Problem: Given a sorted array which might be rotated at some pivot which is not known beforehand, search the index of the target value in the array. All the elements of the array are distinct. Leetcode problem link - https://leetcode.com/problems/search-in-rotated-sorted-array/
Note: The complexity of the algorithm should be O(logn).
Example: Let the given array be, [4, 5, 6, 0, 1, 2]. And the target value is 1. The index of 1 returned will be 4.
The problem can be solved with the help of binary search technique. Given below is the code explained in Java -
<div class="code">
public int search(int[] nums, int target) {
//call binSearch function
return binSearch(nums, 0, nums.length-1, target);
}
public int binSearch(int nums[], int left, int right, int target){
if(nums == null || nums.length == 0) return -1;
//if there are only 1 or 2 elements in the array.
if(left == right || left == right-1){
if(nums[left] == target) return left;
if(nums[right] == target) return right;
return -1;
}
// calculate the mid index.
int mid = left + (right - left) /2;
if(nums[mid] == target){
return mid;
}
//the array will be divided into 2 parts. In both the parts, the range
//of the target value will be searched.
if(nums[mid] > nums[left]){
//if the target lies between left to mid index
if(target >= nums[left] && target <= nums[mid]){
return binSearch(nums, left, mid, target);
}
//if the target lies between mid to right index.
else
return binSearch(nums, mid, right, target);
}
else{
//if the target lies between mid to right index.
if(target >= nums[mid] && target <= nums[right]){
return binSearch(nums, mid, right, target);
}
else
//if the target lies between left to mid index
return binSearch(nums, left, mid, target);
}
}
</div> Code explanation with example -
Let the array given be [4, 5, 6, 0, 1, 2].
- The algorithm will first find the mid index, which is 2.
- Now the element at index 2, which is 6 is greater than first element, i.e. 4, so the first if condition will be executed and the array is divided in two halves which are sorted.
- Now the algorithm will find the range for target value. We can see that the target lies in the second half, so the function will be called in the second half of the array.
- The algorithm will repeat again until the target index is found.
