範囲を半分に割り、答えが入っていないほうを捨てる。1回で候補が半分になるので O(log n)（100万要素でも20回）。
「ソート済みの配列から値を探す手法」と覚えていると使いどころを見落とす。要るのはどちらの半分を捨ててよいか言えることだけで、探す対象が値である必要はない。
16. Find Minimum in Rotated Sorted Array
https://neetcode.io/problems/find-minimum-in-rotated-sorted-array/question?list=blind75
昇順の配列を何回か回転させた（末尾の何個かが先頭に移った）ものから、最小値を O(log n) で返す。
[4, 5, 6, 7, 0, 1, 2]
↓ ここだけ下がる（段差）
---昇順--- --昇順--
↑ 最小値は段差の直後
何回転させても下がる箇所は1つだけ。つまり探すのは値ではなく段差の直後の位置になる。
捨てる根拠は真ん中 m と右端 r の比較で作れる。
nums[m] < nums[r]→m〜rは下がっていない = 段差は左。最小はmか、その左nums[m] > nums[r]→ あいだで下がっている = 段差は右。最小はmより右
class Solution {
// 例: nums = [4, 5, 6, 7, 0, 1, 2] -> 0
findMin(nums: number[]): number {
let l = 0;
let r = nums.length - 1;
// 「答えは必ず [l, r] の中にいる」を保ったまま、範囲を半分にしていく
while (l < r) {
const m = Math.floor((l + r) / 2);
// 最小は m か、その左。m はまだ候補なので捨てない
if (nums[m] < nums[r]) r = m;
// 最小は m より右。m が最小でないことは確定しているので飛ばせる
else l = m + 1;
}
// l と r が同じ位置まで詰まった = そこが段差の直後
return nums[l];
}
}
時間 O(log n)、空間 O(1)。左右の更新が m + 1 と m で非対称なのは、m 自身を捨ててよいかが違うから。
nums[m] > nums[r]=mは**段差の手前（大きいほうの並び）**にいる。最小は段差の直後なので必ずmより右 →mを捨ててl = m + 1nums[m] < nums[r]=mは**段差の向こう（小さいほうの並び）**にいる。m自身が段差の直後（＝最小）かもしれない → 捨てられないのでr = m - 1ではなくr = m
[4, 5, 6, 7, 0, 1, 2]
m r 7 > 2 -> m は左の並び。最小は m より右
[4, 5, 6, 7, 0, 1, 2]
m r 0 < 2 -> m は右の並び。m 自身が最小かもしれない
ループ条件が l <= r でなく l < r なのは、[l, r] に必ず答えが残っているから。幅が1に潰れた時点でそれが答えなので、「見つけたら返す」判定が要らない。
l=0 r=6 m=3 nums[3]=7 > nums[6]=2 -> 段差は右。l=4
l=4 r=6 m=5 nums[5]=1 < nums[6]=2 -> 段差は左。r=5
l=4 r=5 m=4 nums[4]=0 < nums[5]=1 -> 段差は左。r=4
l===r=4 -> nums[4] = 0
応用: 二分探索が使えるかは「m を見て片側を捨てる根拠が言えるか」で決まる。ここではそれが「右端との大小」だった。
17. Search in Rotated Sorted Array
https://neetcode.io/problems/find-target-in-rotated-sorted-array/question?list=blind75
回転済みの配列から target の添字を返す。無ければ -1。
回転済みの配列は昇順の並びが2本つながったもの。段差の位置は 16（Find Minimum in Rotated Sorted Array）で求めたので、そこで割ってしまえば、ただのソート済み配列が2本になる。あとは両方に教科書どおりの二分探索をかけるだけ。
class Solution {
// 例: nums = [4, 5, 6, 7, 0, 1, 2], target = 0 -> 4
search(nums: number[], target: number): number {
// 段差の直後 = 小さいほうの並びの先頭
const pivot = this.findMinIndex(nums);
const left = this.binarySearch(nums, target, 0, pivot - 1);
return left !== -1 ? left : this.binarySearch(nums, target, pivot, nums.length - 1);
}
// 16 と同じ
private findMinIndex(nums: number[]): number {
let l = 0;
let r = nums.length - 1;
while (l < r) {
const m = Math.floor((l + r) / 2);
if (nums[m] < nums[r]) r = m;
else l = m + 1;
}
return l;
}
// 範囲 [l, r] だけを見る、ふつうの二分探索
private binarySearch(nums: number[], target: number, l: number, r: number): number {
while (l <= r) {
const m = Math.floor((l + r) / 2);
if (nums[m] === target) return m;
if (nums[m] < target) l = m + 1;
else r = m - 1;
}
return -1;
}
}
二分探索が最大2回なので O(log n)、空間 O(1)。
- ループ条件が
l < rとl <= rで違うのは、答えが必ずあるかの差。最小値は必ずいるので幅1に潰れた時点で確定、targetは無いかもしれないので範囲が空になるまで回す
応用: 新しく見える問題でも、すでに解いた問題に帰着できないかをまず考える。ここでは 16（段差探し）が済んでいたので、残りは教科書どおりの二分探索だった。