In the Leetcode Search in Rotated Sorted Array problem solution There is an integer array nums sorted in ascending order (with distinct values).
Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]. For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].
Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.
You must write an algorithm with O(log n) runtime complexity.
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
Example 3:
Input: nums = [1], target = 0
Output: -1
Constraints:
- 1 <= nums.length <= 5000
- -104 <= nums[i] <= 104
- All values of nums are unique.
- nums is an ascending array that is possibly rotated.
- -104 <= target <= 104
Solution in C Programming
int binarySearch(int* nums, int start, int end, int target) {
int middle = (end - start) / 2 + start;
if(start > end) {
return -1;
}
if(nums[middle] == target) {
return middle;
}
else if(nums[middle] > target) {
return binarySearch(nums, start, middle - 1, target);
}
else {
return binarySearch(nums, middle + 1, end, target);
}
return -1;
}
int search(int* nums, int numsSize, int target) {
int i, j;
//search pivot index at first, we can compare start and end
for(i = 0, j = numsSize - 1; i < j; i++, j--) {
if(nums[i] <= nums[j]) { // j is the pivot index
break;
}
else {
if(nums[i] == target) {
return i;
}
else if(nums[j] == target) {
return j;
}
}
}
//after pivot index is found, we can use binary search to find the target in remain sorted array
return binarySearch(nums, i, j, target);
}Solution in C++ Programming
class Solution {
public:
int search(vector<int>& nums, int target) {
int low=0, high=nums.size()-1;
while(low<=high)
{
int mid=(low+high)>>1;
if(target==nums[mid])
return mid;
else if(nums[low]<=nums[mid])
{
if(target>=nums[low] && target<nums[mid])
high=mid-1;
else
low=mid+1;
}
else{
if(target<=nums[high] && target>nums[mid])
low=mid+1;
else
high=mid-1;
}
}
return -1;
}
};Solution in Java Programming
class Solution {
static int i,j;
public int search(int[] a, int n) {
for(int i=0;i<a.length;i++)
{
if(n==a[i])
return i;
}
return -1;
}
}
Solution in Python Programming
class Solution(object):
def search(self, nums, target):
low=0
high=len(nums)-1
while(low<=high):
mid=(low+high)//2
if(nums[mid]==target):
return mid
if(nums[low]<=nums[mid]):
if(target>=nums[low] and target<=nums[mid]):
high=mid-1
else:
low=mid+1
else:
if(target>=nums[mid] and target<=nums[high]):
low=mid+1
else:
high=mid-1
return -1Solution in C# Programming
public class Solution {
public int Search(int[] nums, int target) {
int start = 0;
int end = nums.Length - 1;
// idea is that from the mid atleast one half is sorted, code checks which half is sorted and if
// target lies between sorted half we search target in that otherwise it searhces target in non sorted half code updates start end accordingly.
while(start <= end)
{
// to handle integer overflow
int mid = start + (end - start)/2;
if(nums[mid] == target)
return mid;
// check if this half is sorted
else if (nums[mid] < nums[end])
{
if(target > nums[mid] && target <= nums[end])
start = mid + 1;
else
end = mid-1;
}
// if above is not sorted than this must be
else
{
if(target >= nums[start] && target < nums[mid])
end = mid -1;
else
start = mid+1;
}
}
return -1;
}
}Also read,