0Pricing
Coding Interview Prep · レッスン

First True: 述語二分探索

単調な yes/no の境界を探索します

「First True: 述語二分探索」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。

真偽値の境界を探す

多くの問題には、単調な述語が隠れています。false、false、そしてその後は永遠に true という形です。ソート済み配列がなくても、二分探索で最初の true を見つけられます。

# FFFFTTTT  -> find first T

単調とは何か

述語が単調であるとは、一度 true になったらその後も true のままであることです。この性質があるからこそ、境界を二分探索できます。

def ok(x):
    return x * x >= target

答えの範囲を定める

境界が確実に含まれる範囲を選びます。low は最小の候補に、high は ok が確実に true になる値に設定してください。

low, high = 0, 10**9

中央をテストする

mid を取り、ok(mid) を呼び出します。真偽値の結果によって、通常の二分探索で値を比較する場合と同じように、どちらの半分を残すかが決まります。

mid = (low + high) // 2
if ok(mid):
    ...

True ならもっと小さい可能性がある

ok(mid) が true なら、mid は有効な答えですが、もっと小さい値でもよいかもしれません。high = mid と設定し、mid - 1 にはしないでください。

if ok(mid):
    high = mid

False ならもっと大きい方へ

ok(mid) が false なら、境界は mid より上にあります。low = mid + 1 として、mid とそれ以下をすべて捨ててください。

else:
    low = mid + 1

low が high 未満の間ループする

while low < high を使い、less-than-or-equal にはしません。二つのポインタは最初の true のインデックスに収束し、そこでループが停止します。

while low < high:
    mid = (low + high) // 2

答えは low

ループが終了すると、low は high と等しくなり、両方が最初の true の値を指します。探していた境界として low を返してください。

return low  # first x where ok(x)

high = mid が機能する理由

mid が答えになる可能性があるため、mid を飛ばしてはいけません。high = mid とすれば、範囲を狭めながら mid を範囲内に残せるため、必ず処理が進みます。

high = mid  # mid stays a candidate

整数平方根の例

x*x が n 以下となる最大の x を求めるには、x*x > n が最初に true になる位置を探索し、そこから一つ戻ります。このパターンはそのまま再利用できます。

def ok(x):
    return x * x > n
# answer is found_index - 1

一つのテンプレートで多くの問題に対応する

このfirst-true テンプレートは、実行可能な最小値、最も左のインデックス、最小の容量など、数え切れないほどの問題を解決します。一度覚えれば、どこでも再利用できます。

# low<high, ok->high=mid, else low=mid+1

確認

候補を残すための操作を明確にしてください。

まとめ：最初の true を見つける

これで問題を単調な述語に置き換え、境界を二分探索できるようになりました。high = mid と while low < high の組み合わせが安全なパターンです。🧭

よくある質問

「First True: 述語二分探索」レッスンは無料ですか？

はい。「First True: 述語二分探索」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。

「First True: 述語二分探索」で何を学びますか？

単調な yes/no の境界を探索します ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Coding Interview Prepを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。

「First True: 述語二分探索」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCoding Interview Prepレッスンでコードを書いて実行できますか？

はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. バグのない基本的な二分探索
  2. bisect_left と bisect_right
  3. First True: 述語二分探索
  4. 答えに対する二分探索
← Coding Interview Prepに戻る