問題
小さいnums を[3, 7, 11, 15, 18, 22] を 11 の[15, 18, 22, 3, 7, 11] にtarget が nums の-1 を
numsの値は どれも違います numsの長さは 1 以上 5000 以下、 値と targetはどれも -10000 以上 10000 以下です - 先頭から 1 つずつ
見る O(n) ではなく、 O(log n) で 探してください
入力と出力の例
例 1
22 の
入力
nums = [15, 18, 22, 3, 7, 11]
target = 7出力
4例 2
25 は
入力
nums = [30, 40, 10, 20]
target = 25出力
-1例 3
値が 1 つだけの
入力
nums = [6]
target = 6出力
0面接での聞かれ方
面接では、
- 「ソート済みの
配列を 回転させた 物から、 値を 探してください。 O(log n) で お願いします」 - 最初に O(n) の
書き方を 出すと、 「並びの 形を もう 少し 使えませんか？」と 寄せられます - 書き終えた
あとに 「同じ 値が 入っていても よいとしたら、 どこが 壊れますか？」 「切れ目の 位置だけを 返せますか？」と 広げて 聞かれます
二分探索のlo と hi が
アルゴリズムのチートシートの「ソートと二分探索」に、この型の要点を表とコードでまとめています。
まず
段 1
まずは、
段 2
並びをmid で 2 つにnums[lo] <= nums[mid] なら
段 3
順にtarget が
段 4
毎回、lo から hi までのlo <= hi の
解答
Python
Python
def search_rotated(
nums, target
):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
m = nums[mid]
if m == target:
return mid
a = nums[lo]
b = nums[hi]
if a <= m:
if a <= target < m:
hi = mid - 1
else:
lo = mid + 1
elif m < target <= b:
lo = mid + 1
else:
hi = mid - 1
return -1JavaScript
JavaScript
function searchRotated(
nums, target
) {
let lo = 0;
let hi = nums.length - 1;
while (lo <= hi) {
const mid = (lo + hi) >> 1;
const m = nums[mid];
if (m === target) {
return mid;
}
const a = nums[lo];
const b = nums[hi];
if (a <= m) {
const inA = a <= target;
if (inA && target < m) {
hi = mid - 1;
} else {
lo = mid + 1;
}
} else {
const inB = target <= b;
if (m < target && inB) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
}
return -1;
}Go
Go
func searchRotated(
nums []int, target int,
) int {
lo, hi := 0, len(nums)-1
for lo <= hi {
mid := (lo + hi) / 2
m := nums[mid]
if m == target {
return mid
}
a, b := nums[lo], nums[hi]
if a <= m {
inA := a <= target
if inA && target < m {
hi = mid - 1
} else {
lo = mid + 1
}
} else {
inB := target <= b
if m < target && inB {
lo = mid + 1
} else {
hi = mid - 1
}
}
}
return -1
}a <= m の <= は、lo と mid が< に
計算量
- 時間は O(log n) です。
1 回まわる ごとに、 残りの 区間が およそ 半分になります - 使う
記憶は O(1) です。 lo、hi、midなどの決まった 数の 置き場だけを使います
よく
nums[lo] < nums[mid]と書く。loとmidが同じ 位置の とき、 右半分を 順に 並んだ側と 取り 違えます。 [3, 1]で 1 を探すと、 右半分の 左端を nums[mid]の 3 と見て 「3 より 大きくないので 右には 無い」と 決め、 見落とします - 範囲の
比べで 端を落とす。 左半分に 入るかは nums[lo] <= target < nums[mid]です。nums[lo] < targetと書くと、 targetがちょうど nums[lo]のときに 見落とします。 右半分も target <= nums[hi]と端を含めます - 先に
切れ目を 探してから 2 回目の 二分探索を する とき、 番号を ずらし忘れる。 この 書き方も O(log n) で 正しいのですが、 切れ目より 後ろを 探した 位置を 元の 番号に 戻す所で 1 つずれがちです。 1 回の 二分探索で 済ませると、 ずれる 所が ありません - 同じ値が
ある 並びに そのまま使う。 [2, 2, 2, 5, 2]のように両端と 真ん中が 同じだと、 どちらが 順に 並んだ 側か 決められません。 この 問題では 値が どれも 違うので 起きませんが、 聞かれたら 「その ときは loを 1 つ進めるしかなく、 最悪 O(n) に なります」と答えます
解答を動かした版 Python 3.12.14Node.js 22.23.4Go 1.24.6確認日 2026年10月30日
面接での
書き始める
「先頭から
見れば O(n) で 解けますが、 並びは 1 か所で 切れているだけなので、 真ん中で 割ると 片方は 必ず 小さい 順です。 その側の 両端を 見れば targetが入り得るかが 分かるので、 入り得る 側へ 狭める 二分探索にします。 毎回 半分に なるので 時間は O(log n)、 記憶は O(1) です。」
書き終えたら、
「例 1 で 7 を
探します。 最初は 真ん中が 22 で、 左端の 15 は 22 以下なので 左半分が 順です。 7 は 15 から 22 の 間に 無いので 右へ 進み、 残りは 3、 7、 11 です。 真ん中が 7 なので、 位置 4 を 返します。」