class Solution {
public:
int search(vector<int>& nums, int target) {
}
};
33. 搜索旋转排序数组
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1
示例 3：
输入：nums = [1], target = 0 输出：-1
提示：
1 <= nums.length <= 5000-104 <= nums[i] <= 104nums 中的每个值都 独一无二nums 在预先未知的某个下标上进行了旋转-104 <= target <= 104原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 2.5 MB, 提交时间: 2024-04-22 09:38:30
func search(nums []int, target int) int {
isBlue := func(i int) bool {
end := nums[len(nums)-1]
if nums[i] > end {
return target > end && nums[i] >= target
}
return target > end || nums[i] >= target
}
left, right := -1, len(nums)-1 // 开区间 (-1, n-1)
for left+1 < right { // 开区间不为空
mid := left + (right-left)/2
if isBlue(mid) { // 蓝色
right = mid
} else { // 红色
left = mid
}
}
if nums[right] != target {
return -1
}
return right
}
cpp 解法, 执行用时: 0 ms, 内存消耗: 13.3 MB, 提交时间: 2024-04-22 09:38:11
class Solution {
public:
int search(vector<int> &nums, int target) {
auto is_blue = [&](int i) -> bool {
int end = nums.back();
if (nums[i] > end) {
return target > end && nums[i] >= target;
}
return target > end || nums[i] >= target;
};
int left = -1, right = nums.size() - 1; // 开区间 (-1, n-1)
while (left + 1 < right) { // 开区间不为空
int mid = left + (right - left) / 2;
if (is_blue(mid)) right = mid; // 蓝色
else left = mid; // 红色
}
return nums[right] == target ? right : -1;
}
};
java 解法, 执行用时: 0 ms, 内存消耗: 40.9 MB, 提交时间: 2024-04-22 09:38:00
class Solution {
public int search(int[] nums, int target) {
int left = -1, right = nums.length - 1; // 开区间 (-1, n-1)
while (left + 1 < right) { // 开区间不为空
int mid = left + (right - left) / 2;
if (isBlue(nums, target, mid)) right = mid; // 蓝色
else left = mid; // 红色
}
return nums[right] == target ? right : -1;
}
private boolean isBlue(int[] nums, int target, int i) {
int end = nums[nums.length - 1];
if (nums[i] > end) {
return target > end && nums[i] >= target;
}
return target > end || nums[i] >= target;
}
}
python3 解法, 执行用时: 37 ms, 内存消耗: 16.7 MB, 提交时间: 2024-04-22 09:37:43
# 一次二分
class Solution:
def search(self, nums: List[int], target: int) -> int:
def is_blue(i: int) -> bool:
end = nums[-1]
if nums[i] > end:
return target > end and nums[i] >= target
else:
return target > end or nums[i] >= target
left, right = -1, len(nums) - 1 # 开区间 (-1, n-1)
while left + 1 < right: # 开区间不为空
mid = (left + right) // 2
if is_blue(mid): # 蓝色
right = mid
else: # 红色
left = mid
return right if nums[right] == target else -1
python3 解法, 执行用时: 24 ms, 内存消耗: 15.2 MB, 提交时间: 2022-08-02 15:40:25
class Solution:
def search(self, nums: List[int], target: int) -> int:
if not nums:
return -1
l, r = 0, len(nums) - 1
while l <= r:
mid = (l + r) // 2
if nums[mid] == target:
return mid
if nums[0] <= nums[mid]:
if nums[0] <= target < nums[mid]:
r = mid - 1
else:
l = mid + 1
else:
if nums[mid] < target <= nums[len(nums) - 1]:
l = mid + 1
else:
r = mid - 1
return -1