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. Example 1:Input: nums = [4,5,6,7,0,1,2], target = 0Output: 4Example 2:Input: nums = [4,5,6,7,0,1,2], target = 3Output: -1Example 3:Input: nums = [1], target = 0Output: -1 Constraints:1 <= nums.length <= 5000-104 <= nums[i] <= 104All values of nums are unique.nums is an ascending array that is possibly rotated.-104 <= target <= 104
Question
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. Example 1:Input: nums = [4,5,6,7,0,1,2], target = 0Output: 4Example 2:Input: nums = [4,5,6,7,0,1,2], target = 3Output: -1Example 3:Input: nums = [1], target = 0Output: -1 Constraints:1 <= nums.length <= 5000-104 <= nums[i] <= 104All values of nums are unique.nums is an ascending array that is possibly rotated.-104 <= target <= 104
Solution 1
Here is a Python solution using binary search, which has a time complexity of O(log n):
def search(nums, target):
if not nums:
return -1
low, high = 0, len(nums) - 1
while low <= high:
mid = (low + high) // 2
if target == nums[mid]:
return mid
if nums[low] <= nums[mid]:
if nums[low] <= target <= nums[mid]:
high = mid - 1
else:
low = mid + 1
else:
if nums[mid] <= target <= nums[high]:
low = mid + 1
else:
high = mid - 1
return -1
This function works by first checking if the middle element is the target. If it is, we return the index. If it's not, we need to decide whether to search in the left half or the right half of the array. We do this by checking if the left half is sorted (i.e., nums[low] <= nums[mid]). If it is, and the target lies within this range (nums[low] <= target <= nums[mid]), we search in the left half, i.e., we update high to mid - 1. Otherwise, we search in the right half, i.e., we update low to mid + 1. If the left half is not sorted, that means the right half is sorted. We apply a similar logic for the right half. If the target lies within this range (nums[mid] <= target <= nums[high]), we search in the right half, i.e., we update low to mid + 1. Otherwise, we search in the left half, i.e., we update high to mid - 1. We continue this process until we either find the target or exhaust the array.
Solution 2
Here is a Python solution using binary search, which has a time complexity of O(log n):
def search(nums, target):
if not nums:
return -1
low, high = 0, len(nums) - 1
while low <= high:
mid = (low + high) // 2
if target == nums[mid]:
return mid
if nums[low] <= nums[mid]:
if nums[low] <= target <= nums[mid]:
high = mid - 1
else:
low = mid + 1
else:
if nums[mid] <= target <= nums[high]:
low = mid + 1
else:
Similar Questions
Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:[4,5,6,7,0,1,2] if it was rotated 4 times.[0,1,2,4,5,6,7] if it was rotated 7 times.Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].Given the sorted rotated array nums of unique elements, return the minimum element of this array.You must write an algorithm that runs in O(log n) time.
Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order. Example 1:Input: nums = [1,2,3]Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]Example 2:Input: nums = [0,1]Output: [[0,1],[1,0]]Example 3:Input: nums = [1]Output: [[1]] Constraints:1 <= nums.length <= 6-10 <= nums[i] <= 10All the integers of nums are unique.
You are given an integer array nums sorted in non-decreasing order.Build and return an integer array result with the same length as nums such that result[i] is equal to the summation of absolute differences between nums[i] and all the other elements in the array.In other words, result[i] is equal to sum(|nums[i]-nums[j]|) where 0 <= j < nums.length and j != i (0-indexed). Example 1:Input: nums = [2,3,5]Output: [4,3,5]Explanation: Assuming the arrays are 0-indexed, thenresult[0] = |2-2| + |2-3| + |2-5| = 0 + 1 + 3 = 4,result[1] = |3-2| + |3-3| + |3-5| = 1 + 0 + 2 = 3,result[2] = |5-2| + |5-3| + |5-5| = 3 + 2 + 0 = 5.Example 2:Input: nums = [1,4,6,8,10]Output: [24,15,13,15,21]
Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.You must write an algorithm with O(log n) runtime complexity. Example 1:Input: nums = [1,3,5,6], target = 5Output: 2Example 2:Input: nums = [1,3,5,6], target = 2Output: 1Example 3:Input: nums = [1,3,5,6], target = 7Output: 4 Constraints:1 <= nums.length <= 104-104 <= nums[i] <= 104nums contains distinct values sorted in ascending order.-104 <= target <= 104
Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.