回転済み配列と未ソート配列の二分探索
各ステップでどちらの半分がソート済みかを判断し、search-in-rotated-sorted-arrayとfind-minimum-in-rotated-arrayを解きます。
「回転済み配列と未ソート配列の二分探索」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン2/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
回転ソート済み配列とは
回転ソート済み配列とは、ソート済み配列をあるピボットで分割し、2つの部分を入れ替えたものです。たとえば、[4, 5, 6, 7, 0, 1, 2] は、ソート済み配列 [0,1,2,4,5,6,7] をインデックス4で回転させたものです。この配列は全体としてはソートされていないため、標準的な二分探索は機能しません。
重要な洞察は、どのように回転させても、配列の少なくとも片方の半分は常にソート済みであることです。二分探索では、境界をどちらに移動するか決める前に、どちらの半分がソート済みかを特定する必要があります。
# A rotated sorted array — one half is always sorted
arr = [4, 5, 6, 7, 0, 1, 2]
# Left half [4,5,6,7] is sorted
# Right half [0,1,2] is also sorted
# But left[0]=4 > right[-1]=2 => rotation happened in left-to-right crossingソート済みの半分を特定する
midを計算したら、arr[lo]とarr[mid]を比較します。arr[lo] <= arr[mid]であれば、左半分がソート済みです。そうでなければ、右半分がソート済みです。どちらの半分がソート済みかが分かれば、ターゲットがそのソート済み範囲に含まれるかを確認し、それに応じて探索範囲を絞り込めます。
この判断によって、1ステップごとに配列を正確に半分ずつ破棄できるため、回転された配列でもO(log n)の計算量を維持できます。
def search_rotated(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if nums[mid] == target:
return mid
# Left half is sorted
if nums[lo] <= nums[mid]:
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
# Right half is sorted
else:
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1
print(search_rotated([4, 5, 6, 7, 0, 1, 2], 0)) # 4
print(search_rotated([4, 5, 6, 7, 0, 1, 2], 3)) # -1例を追跡する
search_rotated([4,5,6,7,0,1,2], 0)の処理を、ステップごとに追跡してみます。最初はlo=0, hi=6, mid=3, arr[mid]=7です。ターゲットの0はソート済みの左半分[4..7]にあるでしょうか。いいえ、ありません。そのためlo=4に移動します。次にlo=4, hi=6, mid=5, arr[mid]=1です。左半分[0,1]はソート済みです（arr[lo]=0 <= arr[mid]=1）。0は[0..1)にあるでしょうか。はい、あるためhi=4に設定します。最後にlo=4, hi=4, mid=4, arr[4]=0となり、インデックス4で見つかります。
# Step-by-step trace
nums = [4, 5, 6, 7, 0, 1, 2]
target = 0
steps = []
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
steps.append(f'lo={lo} hi={hi} mid={mid} val={nums[mid]}')
if nums[mid] == target:
steps.append(f'Found at {mid}')
break
if nums[lo] <= nums[mid]:
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else:
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
for s in steps:
print(s)回転配列で重複を扱う
回転された配列に重複が含まれる可能性がある場合（例：[1,3,1,1,1]）、nums[lo] == nums[mid]という条件は曖昧になります。どちらの半分がソート済みなのか判断できないためです。安全な対処法は、loを1増やす（またはhiを1減らす）ことで、もう一度試すことです。これにより最悪時の計算量はO(n)まで悪化するため、面接官には必ず伝えてください。
def search_rotated_with_dups(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if nums[mid] == target:
return True
# Ambiguous: shrink left boundary
if nums[lo] == nums[mid] == nums[hi]:
lo += 1
hi -= 1
elif nums[lo] <= nums[mid]:
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else:
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return False
print(search_rotated_with_dups([1, 3, 1, 1, 1], 3)) # True
print(search_rotated_with_dups([2, 2, 2, 0, 2], 0)) # True回転されたソート済み配列の最小値を求める
関連する問題として、特定のターゲットを探すのではなく、回転されたソート済み配列の最小要素を求めるものがあります。最小値は常にソートされていない半分にあります。各ステップでは、arr[mid] > arr[hi]なら最小値は右半分にあるため（lo = mid + 1）、そうでなければmidを含む左半分にあるためhi = midとします。lo == hiになったとき、最小値が見つかっています。
def find_min(nums):
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if nums[mid] > nums[hi]:
lo = mid + 1 # min is in right half
else:
hi = mid # min is at mid or left of mid
return nums[lo]
print(find_min([3, 4, 5, 1, 2])) # 1
print(find_min([4, 5, 6, 7, 0, 1, 2])) # 0
print(find_min([11, 13, 15, 17])) # 11 (no rotation)arr[lo] <= arr[mid] で左半分がソート済みだと分かる理由
arr[lo] <= arr[mid]という条件が機能するのは、ソート済み（または回転されていない）区間では、先頭の要素が常に最小だからです。arr[lo] <= arr[mid]なら、[lo..mid]の範囲内では回転が起きていないため、その半分はソート済みです。この等号によって、lo == midの場合も扱えます（要素が1つだけの区間は自明にソート済みです）。
逆に、arr[lo] > arr[mid]なら、回転のピボットはloとmidの間にあるはずです。したがって、右半分の[mid..hi]が連続したソート済み区間になります。
# Visualise: detect which half is sorted
examples = [
([4, 5, 6, 7, 0, 1, 2], 0, 6), # mid=3, val=7 => left sorted
([6, 7, 0, 1, 2, 4, 5], 0, 6), # mid=3, val=1 => right sorted
]
for arr, lo, hi in examples:
mid = lo + (hi - lo) // 2
if arr[lo] <= arr[mid]:
print(f'arr[{lo}]={arr[lo]} <= arr[{mid}]={arr[mid]} => LEFT half sorted')
else:
print(f'arr[{lo}]={arr[lo]} > arr[{mid}]={arr[mid]} => RIGHT half sorted')計算量解析
回転されたソート済み配列を二分探索で探索する場合も、計算量はO(log n)、空間計算量はO(1)のままです。各反復で探索範囲を半分にしているためです。通常の二分探索との違いは、どちらの半分がソート済みかを特定する定数時間の確認が追加されることだけです。
重複がある場合、各ステップでloを1つしか増やせないことがあるため、最悪時の計算量はO(n)に悪化します。このトレードオフを明確に説明してください。正常系以外の境界ケースも考慮していることを示せます。
LeetCode 33 の手順
LeetCode 33「回転されたソート済み配列での探索」は、この問題の代表的な形式です。制約により、重複はなく、回転はちょうど1回だけ行われています。解答は、先ほど作成したsearch_rotated関数です。面接での重要なポイントは、重複がないという前提を必ず述べること、境界上の具体例で不等号を確認すること、そして見つかった場合と見つからなかった場合の両方で返されるインデックスが正しいことを確認することです。
# LeetCode 33 — complete solution
def search(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if nums[mid] == target:
return mid
if nums[lo] <= nums[mid]: # left half sorted
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else: # right half sorted
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1
# Tests
print(search([4,5,6,7,0,1,2], 0)) # 4
print(search([4,5,6,7,0,1,2], 3)) # -1
print(search([1], 0)) # -1LeetCode 153: 重複なしで最小値を求める
LeetCode 153「回転されたソート済み配列の最小値」は、重複のない配列から最小値を求める問題です。arr[lo]ではなくarr[hi]とarr[mid]を比較して、最小値がどちら側にあるかを判断します。arr[mid] > arr[hi]なら最小値は右側にあり、そうでなければmidまたはその左側にあります。この方法でO(log n)で最小値に収束します。
def findMin(nums):
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if nums[mid] > nums[hi]:
lo = mid + 1
else:
hi = mid
return nums[lo]
print(findMin([3,4,5,1,2])) # 1
print(findMin([4,5,6,7,0,1,2])) # 0
print(findMin([11,13,15,17])) # 11回転回数とピボットのインデックス
最小要素を見つけられるようになると、回転回数も分かります。最小要素のインデックスは、配列が右方向に何個分回転されたかを正確に示します。たとえば[4,5,6,7,0,1,2]では、最小値がインデックス4にあるため、配列は4個分回転されています。
ピボットが分かれば、インデックスをnを法として扱うことで、通常の二分探索を適用できます。real_idx = (mid + pivot) % nという形です。この別の定式化は、循環インデックス構造を扱う際の考え方を簡単にできます。
def search_via_pivot(nums, target):
n = len(nums)
# Find pivot (index of minimum)
lo, hi = 0, n - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if nums[mid] > nums[hi]:
lo = mid + 1
else:
hi = mid
pivot = lo
# Binary search with offset
lo, hi = 0, n - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
real_mid = (mid + pivot) % n
if nums[real_mid] == target:
return real_mid
elif nums[real_mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
print(search_via_pivot([4,5,6,7,0,1,2], 0)) # 4すべてをまとめる
面接で回転配列の問題に遭遇したら、次の判断手順に従ってください。まず、ターゲットを探す必要があるのか、最小値を探す必要があるのかを判断します。ターゲットを探す場合は、ソート済みの半分を特定する方法を使います。最小値を探す場合は、midとhiを比較します。重複の可能性があるなら、最悪時はO(n)になることを説明し、境界を縮小するフォールバック処理を追加してください。
回転なし、1回だけ回転、最小値が最後の位置に来るように回転した場合という、3つの典型例でコードを追跡して練習してください。
理解度チェック
このレッスンで扱ったData Structures & Algorithms — Coding Interview Prepの概念について、理解度を確認しましょう。
レッスンのまとめ
このレッスンでは、回転されたソート済み配列には常に少なくとも1つのソート済みの半分があること、探索先を決める前にarr[lo]とarr[mid]を比較してソート済みの半分を特定すること、そして最小値を求める場合はarr[mid]とarr[hi]を比較して回転のピボットを特定することを学びました。次は、lower boundとupper boundの二分探索のバリエーションについて学びます。
よくある質問
「回転済み配列と未ソート配列の二分探索」レッスンは無料ですか？
はい。「回転済み配列と未ソート配列の二分探索」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「回転済み配列と未ソート配列の二分探索」で何を学びますか？
各ステップでどちらの半分がソート済みかを判断し、search-in-rotated-sorted-arrayとfind-minimum-in-rotated-arrayを解きます。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン2/4です。
「回転済み配列と未ソート配列の二分探索」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- 古典的な二分探索：左、右、中央
- 回転済み配列と未ソート配列の二分探索
- 下限と上限
- 答えの範囲に対する二分探索