二分探索とDBインデックスについて [AtCoderに入門]

Last updated at 2025-04-11Posted at 2025-04-11

はじめに

最近、自己学習や業務でパフォーマンスを意識したコーディングができていないと感じることが増えてきました。単純な処理なのに実行時間が長すぎるみたいなことがあり、このままじゃマズいなと焦りを感じていました。特に大量データを扱うようになってから、コードの書き方一つでパフォーマンスが大きく変わることを痛感しています。

そこで、パフォーマンスの良いコードを書くためにはアルゴリズムの知識を身に付けたいと興味が湧いてきました。アルゴリズムには苦手意識がありましたがやる気があるうちに学んでいきたいと思います。
目先の目標はAtCoderで水色(Bランク R1200~1599　上位15%)になることです。楽しくコーディングできるようになるまで辛抱して毎日学習していこうと思います。

学習のために購入したのが以下の本です。

アルゴリズム、競技プログラミング

システム・SQL

アルゴリズムの学習と並行して、アプリケーションパフォーマンスにも興味が広がってきました。特にデータベースのクエリ最適化について調べる中で、インデックスの仕組みについても軽く学習して自由自在に使いこなせるようになりたいと思いました。

今回は、自分の学習メモとして、アルゴリズムの基本である二分探索について整理してみました。二分探索とデータベースのインデックスには共通する考え方があり、この関連性を理解することで両方の知識を深められると感じています。この記事は自分の理解を深めるためのものですが、同じように学んでいる方の参考になれば嬉しいです。

二分探索とは

ニ分探索（Binary Search）は、ソート済みの配列から特定の値を見つけるための効率的なアルゴリズムです。線形探索がO(n)の時間複雑度であるのに対し、二分探索はO(log n)という非常に高速な時間複雑度を持ちます。

二分探索の基本的な手順

ソート済みの配列の中央の要素を確認する
探している値と中央の要素を比較する
探している値が中央の要素より小さければ、配列の前半部分で再度探索を行う
探している値が中央の要素より大きければ、配列の後半部分で再度探索を行う
探している値が見つかるか、探索範囲が空になるまで繰り返す

イメージで理解するための参考youtube
https://www.youtube.com/shorts/SFtNiIQZHRQ
https://www.youtube.com/watch?v=i9LAfRbGkT8

Rubyでの基本的な二分探索の実装

def binary_search(array, target)
  # 探索範囲の初期化
  low = 0                 # 探索範囲の下限
  high = array.length - 1 # 探索範囲の上限

  # 探索範囲が存在する限り繰り返す
  while low <= high
    # 中央の要素のインデックスを計算
    # Ruby では整数同士の除算は自動的に切り捨てられる
    mid = (low + high) / 2

    # 中央の要素と目標値を比較
    if array[mid] == target
      return mid          # 目標値が見つかった場合、そのインデックスを返す
    elsif array[mid] < target
      low = mid + 1   # 目標値が中央値より大きい場合、後半部分を探索
    else
      high = mid - 1  # 目標値が中央値より小さい場合、前半部分を探索
    end
  end

  # 目標値が見つからなかった場合は -1 を返す
  return -1
end

# 使用例
arr = [1, 3, 5, 7, 9, 11, 13, 15]
puts binary_search(arr, 9) # => 4 (9は配列の四番目の要素、インデックスは4)
puts binary_search(arr, 6) # => -1 (6は配列に存在しないため-1を返す)

# 二分探索の時間複雑度: O(log n)
# 各ステップで探索範囲が半分になるため、非常に効率的なアルゴリズム
# ただし、配列があらかじめソートされている必要がある

データベースのインデックスと二分探索 (AIに教えてもらったため、合っているかは不明)

データベースのインデックスは、二分探索のアイデアを活用した仕組みです。インデックスを貼ることで、データベースの検索操作が大幅に高速化されます。

インデックスがなぜ検索を高速化するのか (AIに教えてもらったため、合っているかは不明)

データベースにインデックスがない場合、特定のレコードを探すためには全テーブルをスキャン（フルテーブルスキャン）する必要があり、これはO(n)の時間がかかります。一方、インデックスを使用すると、二分探索のようにO(log n)の時間で目的のレコードに到達できます。
具体的には、インデックスは指定したカラムの値をソートした形で別途保存し、各値に対して元のテーブルのどの位置にデータがあるかを示すポインタを持ちます。これにより、条件に合致するデータの位置を二分探索的に素早く特定できるのです。

インデックスを貼るべきカラムの特徴 (AIに教えてもらったため、合っているかは不明)

WHERE句でよく使われるカラム：検索条件に頻繁に使われるカラムにインデックスを貼ると、検索が高速になります。
JOIN操作で使用されるカラム：テーブル結合に使われるカラムにインデックスを貼ると、JOIN操作が高速化されます。
一意性の高いカラム：重複値が少ないカラム（カーディナリティが高いカラム）ほどインデックスの効果が高くなります。例えば、性別（男/女）のような値は種類が少なすぎるためあまり効果がありません。
ORDER BY, GROUP BYでよく使われるカラム：並べ替えや集約にも二分探索的な操作が関わるため、これらの句で使われるカラムにインデックスを貼ると効果的です。

インデックスを貼るべきでないケース (AIに教えてもらったため、合っているかは不明)

更新が頻繁に行われるテーブル：インデックスがあると挿入・更新・削除の度にインデックスも更新する必要があり、処理が遅くなります。
小さなテーブル：レコード数が少ない場合、フルテーブルスキャンの方が効率的なことがあります。
カーディナリティの低いカラム：値の種類が少ないカラムはインデックスの恩恵が少ないです。

データベースのインデックス実装と二分探索の関係 (AIに教えてもらったため、合っているかは不明)

参考記事
B-treeインデックス入門

データベースのインデックスは内部的に「B木」や「B+木」という特殊なデータ構造を使用していることが多いです。これらは二分探索木を拡張したもので、多くの子ノードを持つことができ、ディスクアクセスの回数を減らすよう最適化されています。
しかし基本的な考え方は二分探索と同じで、以下のように動作します：

インデックスの根ノードから探索を開始する
探している値が現在のノードのどの範囲に入るかを判断する
その範囲に対応する子ノードに移動する
目的の値が見つかるまで繰り返す

このようにインデックスは二分探索の考え方を応用し、大量のデータからでも効率的に目的のレコードを見つけられるようにしています。

インデックスの実例

例えば、ユーザーテーブルのemailカラムによく使うクエリがあるとします：

SELECT * FROM users WHERE email = 'example@example.com';

このクエリに対してemailカラムにインデックスがない場合、データベースは全てのレコードを一つずつ調べる必要があります（O(n)）。しかしemailカラムにインデックスを貼ると、二分探索的な手法で目的のレコードを素早く見つけることができます（O(log n)）。
インデックスの作成は以下のようなSQLで行います：

CREATE INDEX index_users_on_email ON users(email);

Rubyで解く二分探索問題

問題1: 挿入位置の検索

ソート済みの配列に新しい値を挿入する位置を二分探索で見つけてください。

def find_insert_position(arr, target)
  low = 0
  high = arr.length - 1

  while low <= high
    # 中央の要素のインデックスを計算
    mid = (low + high) / 2

    # 中央の要素と挿入したい値を比較
    if arr[mid] == target
      return mid          # 同じ値が見つかった場合、そのインデックスを返す
    elsif arr[mid] < target
      low = mid + 1       # 挿入したい値が中央値より大きい場合、右側（後半）を探索
    else
      high = mid - 1      # 挿入したい値が中央値より小さい場合、左側（前半）を探索
    end
  end

  # ループを抜けた時点でのlowが挿入位置となる
  # これは次の理由による：
  # - 探索が終了した時点で、low > high の状態
  # - low は「targetより小さい最後の要素の次の位置」を指している
  return low
end


# テスト例
arr = [1, 3, 5, 7, 9]
puts find_insert_position(arr, 6)  # => 3（6は5(インデックス2)と7(インデックス3)の間に入るため、インデックス3が挿入位置）
puts find_insert_position(arr, 10) # => 5（10は全ての要素より大きいため、配列の最後（length=5の位置）が挿入位置）
puts find_insert_position(arr, 0)  # => 0（0は全ての要素より小さいため、配列の先頭が挿入位置）
puts find_insert_position(arr, 5)  # => 2（5と同じ値がある場合、その位置を返す）

二分探索で値が見つからない場合、以下の流れで進みます：

最初に low = 0, high = arr.length - 1 で初期化します
while low <= high のループの中で探索を続けます
値が見つからない場合は、以下のどちらかの処理を毎回行います：

arr[mid] < target の場合：low = mid + 1 （右側を探索）
arr[mid] > target の場合：high = mid - 1 （左側を探索）

最終的に探索範囲が狭まり続け、値が見つからない場合は以下のようになります：

探索範囲が1要素だけになった時点で、その要素と比較します
その要素がtargetより小さければ low = mid + 1 となり、low > high になります
その要素がtargetより大きければ high = mid - 1 となり、同様に low > high になります

具体例で見てみましょう。配列 [1, 3, 5, 7, 9] で値 6 を探す場合：

low = 0, high = 4, mid = 2 → arr[2] = 5 < 6 なので low = 3
low = 3, high = 4, mid = 3 → arr[3] = 7 > 6 なので high = 2
ここで low = 3, high = 2 となり、low > high なのでループを抜けます

この時の low の値は、ちょうど「targetより小さい最後の要素の次の位置」を指しており、これが適切な挿入位置になります。これは「6」の場合、「5」と「7」の間に入るべき位置なので、インデックス3が正しい挿入位置になります。

問題2: 回転配列の最小値

元々ソートされていた配列が何回か回転された後の配列の最小値を二分探索で見つけてください。

def find_min_in_rotated(arr)
  # 探索範囲の初期化
  left = 0                 # 探索範囲の左端
  right = arr.length - 1   # 探索範囲の右端

  # 左端と右端が一致するまで（つまり、要素が1つになるまで）探索を続ける
  while left < right
    # 中央の要素のインデックスを計算
    mid = (left + right) / 2

    # 配列が回転している場合、最小値は「不連続点」に存在する
    # 中央値と右端の値を比較することで、どちら側に不連続点があるかを判断
    if arr[mid] > arr[right]
      # 中央値が右端の値より大きい場合、不連続点（つまり最小値）は右半分にある
      # 例: [4,5,6,7,0,1,2]の場合、arr[3]=7 > arr[6]=2なので、最小値は右半分にある
      left = mid + 1
    else
      # 中央値が右端の値以下の場合、不連続点は左半分か中央値自身
      # 例: [5,1,2,3,4]の場合、arr[2]=2 < arr[4]=4なので、最小値は左半分かmid自身
      # midが最小値の可能性があるので、midを除外せずrightをmidにする
      right = mid
    end
  end

  # ループを抜けた時点でleftとrightは同じ位置を指し、それが最小値の位置
  return arr[left]
end

# テスト例
puts find_min_in_rotated([4, 5, 6, 7, 0, 1, 2])  # => 0 ([0,1,2,4,5,6,7]が3回右に回転)
puts find_min_in_rotated([3, 4, 5, 1, 2])        # => 1 ([1,2,3,4,5]が2回右に回転)
puts find_min_in_rotated([11, 13, 15, 17])       # => 11 (回転していない場合も正しく動作)
puts find_min_in_rotated([5, 1, 2, 3, 4])        # => 1 ([1,2,3,4,5]が1回右に回転)

# 解説:
# 回転配列の特性：元々ソートされていた配列が回転されると、1箇所だけ「不連続点」ができる。
# この不連続点が最小値の位置である。
#
# このアルゴリズムのポイント:
# 1. 配列の中央値(mid)と右端の値(right)を比較
# 2. もし中央値 > 右端の値なら、不連続点は右半分にある
# 3. もし中央値 <= 右端の値なら、不連続点は左半分（midを含む）にある
#
# 例: [4,5,6,7,0,1,2] の場合の探索過程
# 初期状態: left=0, right=6, mid=3, arr[mid]=7, arr[right]=2
# 7 > 2 なので、left = mid + 1 = 4
# 次の状態: left=4, right=6, mid=5, arr[mid]=1, arr[right]=2
# 1 < 2 なので、right = mid = 5
# 次の状態: left=4, right=5, mid=4, arr[mid]=0, arr[right]=1
# 0 < 1 なので、right = mid = 4
# 最後の状態: left=4, right=4 (ループ終了)
# 結果: arr[left] = arr[4] = 0

問題3: ピークインデックスの検索

山型の配列（最初は増加し、ある点から減少する）のピーク要素のインデックスを二分探索で見つけてください。

def find_peak(arr)
  # 探索範囲の初期化
  left = 0                 # 探索範囲の左端
  right = arr.length - 1   # 探索範囲の右端

  # 左端と右端が一致するまで（つまり、要素が1つになるまで）探索を続ける
  while left < right
    # 中央の要素のインデックスを計算
    mid = (left + right) / 2

    # 山型配列のピークを見つけるため、中央値とその次の値を比較
    if arr[mid] < arr[mid + 1]
      # 中央値が次の値より小さい場合、まだ上昇中なのでピークは右側に存在
      # 例: [1,3,5,7,6,4,2]のmid=2では、arr[2]=5 < arr[3]=7なので、ピークは右側
      left = mid + 1
    else
      # 中央値が次の値以上の場合、すでに下降しているかピーク自体なので、
      # ピークはmid自身かその左側に存在
      # 例: [1,3,5,7,6,4,2]のmid=4では、arr[4]=6 > arr[5]=4なので、ピークはmidか左側
      right = mid
    end
  end

  # ループを抜けた時点でleftとrightは同じ位置を指し、それがピーク要素の位置
  return left
end

# テスト例
puts find_peak([1, 3, 5, 7, 6, 4, 2])  # => 3（値7のインデックス）
puts find_peak([1, 2, 3, 1])           # => 2（値3のインデックス）
puts find_peak([1, 2, 3, 4, 5, 7, 1])  # => 5（値7のインデックス）

# 解説:
# 山型配列の特性：値が最初は増加し、ピークに達した後は減少する
# このアルゴリズムでは、配列内の「どの方向に進めばピークに近づくか」を判断して
# 二分探索の範囲を狭めていきます。
#
# このアルゴリズムのポイント:
# 1. 中央値(mid)とその次の値(mid+1)を比較
# 2. もし arr[mid] < arr[mid+1] なら、まだ上昇中なのでピークは右側
# 3. もし arr[mid] >= arr[mid+1] なら、すでに下降しているかピーク自体なので、ピークはmidか左側
#
# 例: [1,3,5,7,6,4,2] の場合の探索過程
# 初期状態: left=0, right=6, mid=3, arr[mid]=7, arr[mid+1]=6
# 7 > 6 なので、right = mid = 3
# 次の状態: left=0, right=3, mid=1, arr[mid]=3, arr[mid+1]=5
# 3 < 5 なので、left = mid + 1 = 2
# 次の状態: left=2, right=3, mid=2, arr[mid]=5, arr[mid+1]=7
# 5 < 7 なので、left = mid + 1 = 3
# 最後の状態: left=3, right=3 (ループ終了)
# 結果: arr[left] = arr[3] = 7（これがピーク値）

終わりに

アルゴリズムを学ぶ中で、二分探索とデータベースのインデックスに共通する考え方があることを知り、とても興味深く感じました。単純な仕組みでありながら、大きなパフォーマンス向上をもたらす二分探索の原理は、エンジニアとして知っておくべき基本だと実感しています。
今後もAtCoderで水色を目指して学習を続け、業務でもパフォーマンスを意識したコードが書けるようになりたいです。次は動的計画法や探索アルゴリズムについても学んでいく予定です。
この記事が同じようにアルゴリズムを学び始めた方の参考になれば嬉しいです。

株式会社シンシアでは、実務未経験のエンジニアの方や学生エンジニアインターンを採用し一緒に働いています。
※ シンシアにおける働き方の様子はこちら

弊社には年間100人程度の実務未経験の方に応募いただき、技術面接を実施しております。
この記事が少しでも学びになったという方は、ぜひ wantedly のストーリーもご覧いただけるととても嬉しいです！

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up