edubun
日本語
English한국어EspañolPortuguêsFrançaisDeutschItalianoРусский日本語
ホーム›プログラミング›アルゴリズム

探索：線形探索と二分探索

整列した100万人の名前のリストから1人を見つけるのに、二分探索なら20回より多く調べる必要はありません。

1つの値を探す

探索とは、集まりの中で値がどこにあるかを見つける、あるいはそこにないとわかる問題です。連絡先の名前を入力するとスマートフォンが、商品の在庫を確かめるときはお店が、入力した単語ごとにスペルチェッカーが探索をしています。入力はリストと目標の値です。出力は目標の位置か、「見つからない」を意味する -1 のような印です。

線形探索：1つずつ

いちばん素朴な方法は、左から始めて、目標が見つかるかリストが終わるまで値を順に1つずつ調べることです。これが線形探索です。整列していてもいなくても、どんなリストにも使えます。かかる手間は運しだいです。目標が先頭なら1回調べれば十分ですが、最後にあるかリストにないなら、すべての値を調べます。n個の値のリストでは、最悪の場合n回調べます。長さが2倍のリストなら2倍の回数がかかることがあります。「線形」という名前はここから来ています。仕事量が大きさに比例して直線的に増えるのです。

function linearSearch(list, target) {
  for (let i = 0; i < list.length; i++) {
    if (list[i] === target) return i;  // 見つかった
  }
  return -1;                             // すべて調べた
}

二分探索：残りを半分にする

リストが整列していれば、ずっとうまくやれます。数当てゲームを考えてみましょう。だれかが1から100までの数を1つ選び、「もっと大きい」か「もっと小さい」だけを答えます。かしこいプレイヤーは最初に50と言います。答えがどちらでも、可能性の半分が消えます。次は残りの真ん中を言い、これをくり返します。二分探索は整列したリストでまさにこれを行います。目標がまだありうる部分の両端に、lo と hi という2つの目印を置きます。そして真ん中の値を調べます。それが目標なら終わりです。真ん中の値が目標より小さければ、その左側もすべて小さいので、lo を真ん中の先へ動かします。大きければ、hi を真ん中の手前へ動かします。lo が hi を追いこしたら、もう何も残っておらず、目標はリストにありません。

function binarySearch(list, target) {
  let lo = 0, hi = list.length - 1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (list[mid] === target) return mid;
    if (list[mid] < target) lo = mid + 1;  // 目標は右側
    else hi = mid - 1;                     // 目標は左側
  }
  return -1;
}
読み込み中

ドラッグで回転、スクロールまたはピンチで拡大・縮小。

31個の数の整列したリスト。目標を選び、二分探索と線形探索を1ステップずつ進めて、調べた回数を比べましょう。

何回調べる？

二分探索では、1回調べるごとに残りの部分が少なくとも半分になります。n個の値から始めると、1回調べた後に残るのは多くても約n/2個、2回の後は約n/4個、というように1個になるまで続きます。nから1になるまでに必要な半分にする回数が、2を底とするnの対数で、log₂ n と書きます。最後の1回も数に入れると、二分探索に必要なのは多くても ⌊log₂ n⌋ + 1 回です。⌊ ⌋ は切り捨てを表します。100個の値なら7回で、数当てゲームでいつも7回以内に勝てるのはこのためです。1,000個なら10回、100万個なら20回、10億個なら30回です。

リストの大きさ n線形探索、最悪の場合二分探索、最悪の場合
773
1001007
1,0001,00010
1,000,0001,000,00020
1,000,000,0001,000,000,00030

注意点：リストは整列していなければならない

二分探索がうまくいくのは、整列したリストでは1回の比較で目標がどちら側にあるかがわかるからです。整列していないリストでは、真ん中の値は両隣について何も教えてくれないので、線形探索に戻るしかありません。整列にはそれ自体の手間がかかる（次の2つのユニットはその話です）ので、どちらを選ぶかは使い方しだいです。リストを1回だけ探すなら、線形探索がいちばん安上がりかもしれません。同じリストを何千回も探すなら、一度整列してから二分探索を使えば、すぐに元が取れます。データを準備する手間と、そのデータについての問いに答える手間の取引は、この分野全体に出てきます。

二分探索でよくあるまちがいは、更新の手順です。lo = mid + 1 ではなく lo = mid と書くと、値が2つ残ったときに mid が変わらなくなり、ループが永遠に回ることがあります。真ん中の値はもう調べたので、次の範囲から外してかまいません。
線形探索先頭から値を1つずつ調べる
二分探索整列した範囲の真ん中を調べ、目標がありえない半分を捨てる
最悪の場合アルゴリズムの仕事量がいちばん多くなる入力
log₂ nnを半分にしていって1になるまでの回数
lo と hi目標がまだありうる範囲の両端
-1「見つからない」を意味する、よく使われる戻り値
  1. 1,000個の値の整列したリストで、二分探索が調べる回数は多くても何回ですか？
  2. 1,000個の値のリストで、線形探索が調べる回数は多くても何回ですか？
  3. 二分探索を使うには、リストが次のようになっている必要があります
    • 整列している
    • 短い
    • 整数だけでできている
    • 同じ値がくり返し出てこない
  4. リスト [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] で23を見つけるとき、二分探索は何回調べますか？
  5. 同じリストで23を見つけるとき、線形探索は何回調べますか？
  6. 二分探索で25を探しているとき、真ん中の値40を調べました。次にどうなりますか？
    • hi が真ん中のすぐ手前に動く
    • lo が真ん中のすぐ後ろに動く
    • 探索が止まる。25はない
    • 右隣の値を調べる
  7. 1から100までの数を当てるとき、「もっと大きい」か「もっと小さい」かを教えてもらえます。最善の作戦なら、何回当てようとすれば必ず足りますか？
  8. リストの大きさが2倍になりました。二分探索が最悪の場合に調べる回数はどうなりますか？
    • 2倍になる
    • 約1回増える
    • まったく変わらない
    • 2乗になる
  9. 整列していないリストで、1つの値を1回だけ探します。安上がりなのはどちらですか？
    • 線形探索
    • リストを整列してから二分探索する
  10. mid + 1 ではなく lo = mid と書くと、二分探索が永遠にくり返すことがあるのはなぜですか？
    • 値が2つ残ると、mid が毎回同じままになることがある
    • mid が負になる
    • JavaScriptでは許されない
    • リストが長くなる
  11. 1,000,000個の値に対して、二分探索が調べる回数は多くても何回ですか？
ポイント
  • 線形探索は値を1つずつ調べます。最大でn回です。
  • 二分探索は残りの範囲を半分にします。最大で ⌊log₂ n⌋ + 1 回です。
  • 二分探索は整列したリストでしか使えません。
  • 100万個の値でも、調べるのは多くて20回です。
  • mid + 1 と mid − 1 で更新すれば、範囲は必ず小さくなります。
このコースの出典 (11)
  • MIT OpenCourseWare 6.006 Introduction to Algorithms, Spring 2020 (Demaine, Ku, Solomon)
  • lecture notes 1 Introduction, 3 Sorting, 9 Breadth-First Search, 10 Depth-First Search (ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/pages/lecture-notes) and Fall 2011 lecture 13 BFS notes (ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011)
  • Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (MIT Press)
  • with the CLRS-based Khan Academy algorithms unit by Thomas Cormen and Devin Balkcom of Dartmouth (khanacademy.org/computing/computer-science/algorithms: binary search, selection sort analysis, merge sort, quicksort overview and analysis)
  • MacTutor History of Mathematics, Al-Khwarizmi (mathshistory.st-andrews.ac.uk/Biographies/Al-Khwarizmi: word algorithm from the Latin title Algoritmi de numero Indorum)
  • D. E. Joyce, Euclid's Elements Book VII Propositions 1 and 2 (mathcs.clarku.edu/~djoyce/elements/bookVII)
  • Wolfram MathWorld, Merge Sort (mathworld.wolfram.com/MergeSort.html: proposed by John von Neumann in 1945, after Knuth 1998 p. 159)
  • Stanford CS "Tony Hoare: Quicksort" (cs.stanford.edu/people/eroberts/courses/soco/projects/2008-09/tony-hoare/quicksort.html: devised while a student at Moscow State University for Russian-English machine translation with a tape dictionary, programmed in Algol 60 and published 1961; the year 1959 from the Wikipedia Quicksort article and its cited sources)
  • Bodleian Libraries, Ada Lovelace (blogs.bodleian.ox.ac.uk/adalovelace: 1843 paper, Note G Bernoulli numbers)
  • Fourmilab text of Menabrea's Sketch with Lovelace's notes (fourmilab.ch/babbage/sketch.html)
  • Seven Bridges of Konigsberg (Euler 1736) and Tower of Hanoi (Edouard Lucas, 1883) checked against the Wikipedia articles and their cited sources.

確認日: 2026-10-17