题目描述
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如,数组?[0,1,2,4,5,6,7]?可能变为?[4,5,6,7,0,1,2]?)。
搜索一个给定的目标值,如果数组中存在这个目标值,则返回它的索引,否则返回?-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
解题思路
对数组进行二分,分成有序与无序两部分后,依情况继续二分
相关代码
var search = function(nums, target) {
let left = 0,
right = nums.length - 1
while (left < right) {
let mid = Math.ceil((left + right) / 2)
if (nums[mid] === target) {
return mid
}
// [left, mid] 为有序部分时
if (nums[mid] > nums[left]) {
// target 在[left, mid]的区间内
if (nums[left] <= target && nums[mid] >= target) {
right = mid
} else { // target 不在区间内,向乱序部分二分
left = mid
}
} else { // [mid, right] 为有序部分时
if (nums[mid] <= target && nums[right] >= target) {
left = mid
} else {
right = mid
}
}
}
return -1
};
实际看到的错误信息
当测试用例为:search([4,5,6,7,0,1,2], 3) 时,代码会超时,无法正常运行。。。
实在找不出错误,麻烦大家了