二分探索で回された並びのいちばん小さい値を探す

二分探索問題 85

小さい順の並びを途中で切って前後を入れ替えた並びから、いちばん小さい値を O(log n) で返します。まん中と右端を比べて、切れ目のある側へ絞る二分探索の練習です。

海外で定番の問題リスト 4 本には入っていません

問題

整数の並び nums を受け取ります。nums は、小さい順に並んだ並びを、どこか 1 か所で切って、後ろの部分を前へ回した物です。いちばん小さい値を返す関数を書いてください。

  • たとえば [3, 8, 12, 20, 25] を 12 の前で切って回すと [12, 20, 25, 3, 8] になります。切らずにそのままのこともあります
  • 同じ値は 2 回出てきません
  • 要素の数は 1 以上 5000 以下、値はどれも -5000 以上 5000 以下です
  • 時間は O(log n) で解いてください

入力と出力の例

例 1

13 のあとで 1 に下がるところが切れ目です。いちばん小さいのは切れ目のすぐ後ろの 1 です。

nums = [9, 10, 11, 13, 1, 4, 6]
1

例 2

一度も回していない並びです。先頭の -7 がいちばん小さい値です。

nums = [-7, -2, 0, 5, 9]
-7

例 3

いちばん小さい値が最後に来る並びです。

nums = [30, 40, 50, 10]
10

面接での聞かれ方

二分探索で「何と比べてどちらに絞るか」を考えさせる問題として、ミドルの面接でよく出ます。

  • 「回された並びの最小値を、全部を見ずに求めてください」
  • 回された並びから値を探す問題 (この一覧の rotated-array-search) の前置きとして出されることも、続きとして聞かれることもあります。最小値の位置が分かれば、切れ目の左右どちらかでふつうの二分探索ができます
  • 「同じ値があってもよいとしたらどうなりますか？」と続けて聞かれることがあります。まん中と右端が同じだと向きが決まらず、右端を 1 つ縮めるしかないので、いちばん悪いと O(n) になります

ミドルの問題なので、左端ではなく右端と比べる理由を言葉で言えるかが見られます。

ヒント

まだ開いていません

付箋は 4 枚。下の段ほど答えに近づきます

  2. ヒント 2

  3. ヒント 3

  4. ヒント 4答えに近い

アルゴリズムのチートシートの「ソートと二分探索」に、この型の要点を表とコードでまとめています。

関わる学び

二分探索は、並んだデータの範囲を半分ずつ絞ります。100 万件でも 20 回ほどで 1 件になります。

main.py
def rotated_min(nums: list[int]) -> int:
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
print(rotated_min([9, 10, 11, 13, 1, 4, 6]))

できているか「例で確かめる」を押すと、問題の例を全部この関数に渡して、通ったかをここに出します