Open Cosen95 opened 4 years ago
说实话,起初我没看懂这道题目的真正含义,想着用indexOf
就可以啊。
但,打脸来的太快,题目要求时间复杂度O(log n)
,而采用indexOf
的话显然是O(n)
。
其实是想让我们用二分
来解答。
这道题目有一个核心:二分分开的两边,必定有一边是有序的。
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var search = function(nums, target) {
let start = 0,
end = nums.length - 1;
while (start <= end) {
const mid = start + ((end - start) >> 1);
if (nums[mid] === target) return mid
// 至少有一边是有序的
if (nums[mid] >= nums[start]) {
// [start, mid]有序
if (target >= nums[start] && target <= nums[mid]) {
// target在[start, mid]区间
end = mid - 1
} else {
// target不在[start, mid]区间
start = mid + 1
}
} else {
// [mid, end]有序
if (target >= nums[mid] && target <= nums[end]) {
// target在[mid, end]区间
start = mid + 1
} else {
// target不在[mid, end]区间
end = mid - 1
}
}
}
return -1
};
leetcode: https://leetcode-cn.com/problems/search-in-rotated-sorted-array/