Description:
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.
Examples:
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: -1Solution in Python:
To solve this problem, we need to perform a binary search on a rotated sorted array. The key challenge is to determine which part of the array is sorted at each step of the binary search, as this will help us decide which part to continue searching.
Approach:
- Initialize two pointers,
leftandright, to the start and end of the array. - Calculate the middle index,
mid. - Check if the element at
midis the target. If it is, returnmid. - Determine which part of the array is sorted:
- If
nums[left]<=nums[mid], the left part is sorted.- Check if the target lies within this sorted part:
- If
nums[left]<=target<nums[mid], move therightpointer tomid - 1. - Otherwise, move the
leftpointer tomid + 1.
- If
- Check if the target lies within this sorted part:
- If
nums[mid]<nums[right], the right part is sorted.- Check if the target lies within this sorted part:
- If
nums[mid]<target<=nums[right], move theleftpointer tomid + 1. - Otherwise, move the
rightpointer tomid - 1.
- If
- Check if the target lies within this sorted part:
- If
- Repeat the process until
left<=right. - If the target is not found, return -1.
Python
from typing import List
class Solution:
def search(self, nums: List[int], target: int) -> int:
# Use len() function to get the length of the list
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
# Check if the mid element is the target
if nums[mid] == target:
return mid
# Determine which part is sorted
if nums[left] <= nums[mid]:
# Left part is sorted
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
# Right part is sorted
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
# If we exit the loop, the target was not found
return -1
Solution in Javascript:
JavaScript
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var search = function(nums, target) {
// Initialize two pointers to represent the search range
let left = 0;
let right = nums.length - 1;
// Binary search loop
while (left <= right) {
// Calculate the middle index
let mid = Math.floor((left + right) / 2);
// Check if the mid element is the target
if (nums[mid] === target) {
return mid;
}
// Determine which part of the array is sorted
if (nums[left] <= nums[mid]) {
// Left part is sorted
if (nums[left] <= target && target < nums[mid]) {
// Target is in the left sorted part
right = mid - 1;
} else {
// Target is in the right part
left = mid + 1;
}
} else {
// Right part is sorted
if (nums[mid] < target && target <= nums[right]) {
// Target is in the right sorted part
left = mid + 1;
} else {
// Target is in the left part
right = mid - 1;
}
}
}
// If we exit the loop, the target was not found
return -1;
};Solution in Java:
Java
class Solution {
public int search(int[] nums, int target) {
// Initialize two pointers to represent the search range
int left = 0;
int right = nums.length - 1;
// Binary search loop
while (left <= right) {
// Calculate the middle index
int mid = left + (right - left) / 2;
// Check if the mid element is the target
if (nums[mid] == target) {
return mid;
}
// Determine which part of the array is sorted
if (nums[left] <= nums[mid]) {
// Left part is sorted
if (nums[left] <= target && target < nums[mid]) {
// Target is in the left sorted part
right = mid - 1;
} else {
// Target is in the right part
left = mid + 1;
}
} else {
// Right part is sorted
if (nums[mid] < target && target <= nums[right]) {
// Target is in the right sorted part
left = mid + 1;
} else {
// Target is in the left part
right = mid - 1;
}
}
}
// If we exit the loop, the target was not found
return -1;
}
}Solution in C#:
C#
public class Solution {
public int Search(int[] nums, int target) {
// Initialize two pointers to represent the search range
int left = 0;
int right = nums.Length - 1;
// Binary search loop
while (left <= right) {
// Calculate the middle index
int mid = left + (right - left) / 2;
// Check if the mid element is the target
if (nums[mid] == target) {
return mid;
}
// Determine which part of the array is sorted
if (nums[left] <= nums[mid]) {
// Left part is sorted
if (nums[left] <= target && target < nums[mid]) {
// Target is in the left sorted part
right = mid - 1;
} else {
// Target is in the right part
left = mid + 1;
}
} else {
// Right part is sorted
if (nums[mid] < target && target <= nums[right]) {
// Target is in the right sorted part
left = mid + 1;
} else {
// Target is in the left part
right = mid - 1;
}
}
}
// If we exit the loop, the target was not found
return -1;
}
}