算法
Find Element in Rotated Array
在一个排序后再旋转的、元素唯一的数组中，用对数时间找到 target 的下标。
思路
使用二分法：
- 旋转后数组依然会有一半是有序的。
- 每次二分都可判断哪一半是有序的，然后决定 target 在哪一边。
算法步骤
- 用普通二分查找模板
- mid 计算后检查哪一半有序
- 判断 target 是否落在有序区间内
- 如果是，收缩到有序区间
- 否则收缩到另一半
- 循环直到找到或左界大于右界
代码
function findInRotatedArray(
numbers: number[],
target: number,
): number {
let left = 0;
let right = numbers.length - 1;
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
if (numbers[mid] === target) return mid;
if (numbers[left] <= numbers[mid]) {
if (numbers[left] <= target && target < numbers[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
if (numbers[mid] < target && target <= numbers[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}在 GitHub 上编辑
上次更新于