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]]
(0-indexed). 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.
Here’s the [Problem Link] to begin with.
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
Brute Force Solution (Linear Scan)
Intuition & Approach
Check every element until you either hit target
or exhaust the array.
Code Implementation
class Solution:
def search(self, nums: List[int], target: int) -> int:
# Scan each index one by one
for i in range(len(nums)):
# If the current element matches the target
if nums[i] == target:
return i # return index immediately
return -1 # not found
PythonCode Explanation
- Runs through the array sequentially.
- Stops early when
target
is found.
Dry Run
nums = [4,5,6,7,0,1,2]
, target = 0
Loop compares in order: 4, 5, 6, 7 → mismatch; index 4 is 0
→ return 4.
Time & Space Complexity
- Time:
O(n)
– one pass overn
elements. - Space:
O(1)
– constant extra memory.
Conclusion
Works for any array but ignores the sorted-yet-rotated structure, so it’s inefficient for large inputs.
Optimal Solution (Modified Binary Search)
Intuition & Approach
A rotated sorted array still has two sorted halves; at least one half of any sub-array window is ordered.
- Maintain
low
,high
. - Compute
mid
. - If
nums[mid]
matchestarget
, returnmid
. - Determine which half is sorted:
- If
nums[low] ≤ nums[mid]
, the left half is sorted. - Otherwise, the right half is sorted.
- If
- Decide which half to discard by seeing where
target
could lie:- If
target
is within the sorted half’s range, move inside that half; otherwise discard it.
- If
- Loop until
low > high
.
Code Implementation
class Solution:
def search(self, nums: List[int], target: int) -> int:
n = len(nums)
low, high = 0, n - 1
while low <= high:
mid = (low + high) // 2 # middle index
if nums[mid] == target: # target found
return mid
# ----- identify the sorted half -----
if nums[low] <= nums[mid]: # left half is sorted
# target lies within the left half?
if nums[low] <= target <= nums[mid]:
high = mid - 1 # search left half
else:
low = mid + 1 # search right half
else: # right half is sorted
# target lies within the right half?
if nums[mid] <= target <= nums[high]:
low = mid + 1 # search right half
else:
high = mid - 1 # search left half
return -1 # target not found
PythonCode Explanation
- Sorted-half test:
nums[low] ≤ nums[mid]
implies continuous ordering betweenlow
andmid
. - Range check: Compare
target
with the endpoints of that half to decide where to continue. - Each iteration halves the remaining search space just like classic binary search.
Dry Run
nums = [4,5,6,7,0,1,2]
, target = 0
low | mid | high | Sorted half | Action |
---|---|---|---|---|
0 | 3 | 6 | left (4 … 7) | target not inside → search right (low = 4 ) |
4 | 5 | 6 | left (0 … 1) | target inside → narrow right (high = 4 ) |
4 | 4 | 4 | check mid = 0 | found, return 4 |
Time & Space Complexity
- Time:
O(log n)
– halving the window each step. - Space:
O(1)
– only pointers and indices.
Conclusion
By detecting which side of the pivot is still sorted and discarding the other half, this modified binary search finds target
in logarithmic time, fully using the array’s structure for optimal performance.
For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.