Leet Code Problem 33 — Search in Rotated Sorted Array
Given a rotated, sorted array nums (distinct values) and an integer target, find the index of target in nums. If target is not found, return — 1. The solution must have O(logn) complexity.
- Input: nums = [4,5,6,7,0,1,2], target = 0
- Output: 4
- Input: nums = [4,5,6,7,0,1,2], target = 3
- Output: -1
- Input: nums = [1], target = 0
- Output: -1
This code implements a search algorithm to find the index of a target value in a rotated sorted array, leveraging a modified binary search. Here’s a breakdown of the logic:
1. Initial Setup:
- It initializes start to the beginning of the array and end to the last index.
2. Binary Search Loop:
- Inside the loop, it calculates medium as the midpoint between start and end.
- It checks if target matches nums[medium], nums[start], or nums[end]. If any match is found, it immediately returns the corresponding index.
3. Dividing the Search Range:
- The algorithm then determines which half of the array is sorted:
- If nums[start] < nums[medium], the left half is sorted.
- If target lies within the sorted left half, it narrows the search to the left (end = medium — 1); otherwise, it searches the right half (start = medium + 1).
- If the left half is not sorted, it assumes the right half is sorted and performs a similar check:
- If target lies within the sorted right half, it narrows to the right half (start = medium + 1); otherwise, it shifts to the left half (end = medium — 1).
4. Return Condition:
- If the target is not found, the loop exits, and the function returns -1.
This approach ensures that the algorithm performs efficiently with a time complexity of O(logn) by reducing the search space each iteration.
class Solution
{
public:
int search(vector<int> &nums, int target)
{
int start = 0;
int end = nums.size() - 1;
while (start <= end)
{
int medium = (start + ((end - start) / 2));
if (target == nums.at(medium))
{
return medium;
}
if (target == nums.at(start))
{
return start;
}
if (target == nums.at(end))
{
return end;
}
else if (nums.at(start) < nums.at(medium))
{
if (target >= nums.at(start) && target < nums.at(medium))
{
end = medium - 1;
}
else
{
start = medium + 1;
}
}
else
{
if (target > nums.at(medium) && target < nums.at(end))
{
start = medium + 1;
}
else
{
end = medium - 1;
}
}
}
return -1;
}
};
