問題
整数のnums をnums は、
- 隣どうしの
値は 必ず 違います。 頂上は ちょうど 1 つです - 増えるだけの
並び (頂上は 最後 ) や、 減るだけの 並び (頂上は 最初) も あります。 長さが 1 なら頂上は 0 番です numsの長さは 1 以上 1000 以下、 値は どれも -2147483648 以上 2147483647 以下です - 前から 1 つずつ
見る 書き方ではなく、 並びの 長さを n として O(log n) の 手間で 解いてください
入力と出力の例
例 1
9 まで
入力
nums = [1, 4, 7, 9, 6, 2]出力
3例 2
最初から
入力
nums = [10, 8, 5, 3]出力
0例 3
負の
入力
nums = [-5, -2, 0, 3]出力
3面接での聞かれ方
面接では、
- 「山の
形の 並びの、 頂上の 位置を 返してください」 - 前から
見て 下り 始めた 所を 答えると、 「O(log n) に できますか？」と 続けて 聞かれます - 「並びが
小さい 順ではないのに、 なぜ 二分探索が 使えるのですか？」と 理由を 説明させられます
二分探索は
アルゴリズムのチートシートの「ソートと二分探索」に、この型の要点を表とコードでまとめています。
まず
段 1
まず
段 2
真ん中のmid を 1 つnums[mid] < nums[mid + 1] なら、mid よりmid を
段 3
範囲は lo と hi の 2 つのlo < hi のlo = mid + 1、hi = mid です。mid は lo 以上 hi 未満なので、mid + 1 はlo と hi が
解答
Python
Python
def peak_index(nums):
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = (lo + hi) // 2
nxt = nums[mid + 1]
if nums[mid] < nxt:
lo = mid + 1
else:
hi = mid
return loJavaScript
JavaScript
function peakIndex(nums) {
let lo = 0;
let hi = nums.length - 1;
while (lo < hi) {
const mid = (lo + hi) >> 1;
const next = nums[mid + 1];
if (nums[mid] < next) {
lo = mid + 1;
} else {
hi = mid;
}
}
return lo;
}Go
Go
func peakIndex(nums []int) int {
lo, hi := 0, len(nums)-1
for lo < hi {
mid := (lo + hi) / 2
if nums[mid] < nums[mid+1] {
lo = mid + 1
} else {
hi = mid
}
}
return lo
}長さが 1 のlo と hi が
計算量
- 時間は O(log n) です。
1 回比べる ごとに、 範囲が 半分になります - 使う
記憶は O(1) です。 lo、hi、midの 3 つの置き場だけを使います
よく
- 左の
隣と 比べて、 端からはみ出す。 nums[mid - 1]と比べると、 midが 0 のときに 並びの 外を 読みます。 lo < hiの間は mid + 1が必ず中に あるので、 右の 隣と比べます - 下りの
とき hi = mid - 1にする。midが頂上 その ものかもしれないので、 midを捨ててはいけません。 hi = midにします while lo <= hiにする。hi = midと組み合わせると、 loとhiが重なった あとも 繰り返しが 続き、 止まらなくなります - 端の
頂上を忘れる。 増えるだけ、 減るだけの 並びでは、 頂上が 最初か 最後です。 前から 見る 書き方で 「下り始めた所」だけを 探すと、 増えるだけの 並びで 答えが 見つかりません
解答を動かした版 Python 3.12.14Node.js 22.23.4Go 1.24.6確認日 2026年10月30日
面接での
書き始める
「前から
見て 下り 始めた 所を 探せば O(n) で 解けます。 ただ、 真ん中の 値と その 右の 隣を 比べれば、 上りの 途中か 下りの 途中かが 分かります。 上りなら頂上は 右、 下りなら 真ん中を 含む左に あるので、 毎回 半分を 捨てられます。 並びが 小さい 順でなくても、 この 向きで 範囲を 絞れるので 二分探索が 使えます。 時間は O(log n)、 記憶は O(1) です。」
書き終えたら、
「例 1 で
たどります。 範囲は 0 から 5 で、 真ん中は 2 番の 7 です。 右の 9 の 方が 大きいので 上りで、 loを 3 にします。次の 真ん中は 4 番の 6 で、 右の 2 より 大きいので hiを 4 にします。次は 3 番の 9 で、 右の 6 より 大きいので hiを 3 にし、loと重なって 3 を 返します。」