![二分探索とDBインデックスについて [AtCoderに入門] #Ruby - Qiita](https://qiita-user-contents.imgix.net/https%3A%2F%2Fqiita-user-contents.imgix.net%2Fhttps%253A%252F%252Fcdn.qiita.com%252Fassets%252Fpublic%252Farticle-ogp-background-afbab5eb44e0b055cce1258705637a91.png%3Fixlib%3Drb-4.0.0%26w%3D1200%26blend64%3DaHR0cHM6Ly9xaWl0YS11c2VyLXByb2ZpbGUtaW1hZ2VzLmltZ2l4Lm5ldC9odHRwcyUzQSUyRiUyRnMzLWFwLW5vcnRoZWFzdC0xLmFtYXpvbmF3cy5jb20lMkZxaWl0YS1pbWFnZS1zdG9yZSUyRjAlMkYzNDkwMDI3JTJGOGU4ZGIyNWFmOTE2MGYzY2UwZDFmNGIyMGJjODQzNjM4ZjFiMDQwNiUyRnhfbGFyZ2UucG5nJTNGMTczNjI5Mjk0MT9peGxpYj1yYi00LjAuMCZhcj0xJTNBMSZmaXQ9Y3JvcCZtYXNrPWVsbGlwc2UmZm09cG5nMzImcz1iYjViNWE3N2NhZDVlMTVhOWEzYmQ3ZDQyNjRiNWMxNA%26blend-x%3D120%26blend-y%3D462%26blend-w%3D90%26blend-h%3D90%26blend-mode%3Dnormal%26mark64%3DaHR0cHM6Ly9xaWl0YS1vcmdhbml6YXRpb24taW1hZ2VzLmltZ2l4Lm5ldC9odHRwcyUzQSUyRiUyRnMzLWFwLW5vcnRoZWFzdC0xLmFtYXpvbmF3cy5jb20lMkZxaWl0YS1vcmdhbml6YXRpb24taW1hZ2UlMkZhZmM0ZGJhZjAzNThlOGQwYjM0NmM4ZDc1ZWIwMzdiMjVmNjc4MDY5JTJGb3JpZ2luYWwuanBnJTNGMTYwNzc1NjU4OD9peGxpYj1yYi00LjAuMCZ3PTQ0Jmg9NDQmZml0PWNyb3AmbWFzaz1jb3JuZXJzJmNvcm5lci1yYWRpdXM9OCZib3JkZXI9MiUyQ0ZGRkZGRiZmbT1wbmczMiZzPTA1OTIwNWUzN2M4MzdmMmZhM2JhZDVkZjg1NzlmMzYx%26mark-x%3D186%26mark-y%3D515%26mark-w%3D40%26mark-h%3D40%26s%3D3d4ab7e8c3cd428273cbe7459e68b903?ixlib=rb-4.0.0&w=1200&fm=jpg&mark64=aHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZ3PTk2MCZoPTMyNCZ0eHQ9JUU0JUJBJThDJUU1JTg4JTg2JUU2JThFJUEyJUU3JUI0JUEyJUUzJTgxJUE4REIlRTMlODIlQTQlRTMlODMlQjMlRTMlODMlODclRTMlODMlODMlRTMlODIlQUYlRTMlODIlQjklRTMlODElQUIlRTMlODElQTQlRTMlODElODQlRTMlODElQTYlMjAlNUJBdENvZGVyJUUzJTgxJUFCJUU1JTg1JUE1JUU5JTk2JTgwJTVEJnR4dC1hbGlnbj1sZWZ0JTJDdG9wJnR4dC1jb2xvcj0lMjMxRTIxMjEmdHh0LWZvbnQ9SGlyYWdpbm8lMjBTYW5zJTIwVzYmdHh0LXNpemU9NTYmdHh0LXBhZD0wJnM9MGJjN2Y5MGMzZWFmZDg4YTdjMGU3YTJjNmJlYjM4NWM&mark-x=120&mark-y=112&blend64=aHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZ3PTgzOCZoPTU4JnR4dD0lNDBvb3l5MDEyMSZ0eHQtY29sb3I9JTIzMUUyMTIxJnR4dC1mb250PUhpcmFnaW5vJTIwU2FucyUyMFc2JnR4dC1zaXplPTM2JnR4dC1wYWQ9MCZzPWE3MjMyY2MyZDU0MmUzNTUwNTdjNzU0YjljZDMzMWUz&blend-x=242&blend-y=454&blend-w=838&blend-h=46&blend-fit=crop&blend-crop=left%2Cbottom&blend-mode=normal&txt64=5qCq5byP5Lya56S-44K344Oz44K344Ki&txt-x=242&txt-y=539&txt-width=838&txt-clip=end%2Cellipsis&txt-color=%231E2121&txt-font=Hiragino%20Sans%20W6&txt-size=28&s=6cd259229b8ce79f566dc1fb55fe3bd8)
最近、自己学習や業務でパフォーマンスを意識したコーディングができていないと感じることが増えてきました。単純な処理なのに実行時間が長すぎるみたいなことがあり、このままじゃマズいなと焦りを感じていました。特に大量データを扱うようになってから、コードの書き方一つでパフォーマンスが大きく変わることを痛感しています。
そこで、パフォーマンスの良いコードを書くためにはアルゴリズムの知識を身に付けたいと興味が湧いてきました。アルゴリズムには苦手意識がありましたがやる気があるうちに学んでいきたいと思います。
目先の目標は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
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)
# 各ステップで探索範囲が半分になるため、非常に効率的なアルゴリズム
# ただし、配列があらかじめソートされている必要がある
データベースのインデックスは、二分探索のアイデアを活用した仕組みです。インデックスを貼ることで、データベースの検索操作が大幅に高速化されます。
データベースにインデックスがない場合、特定のレコードを探すためには全テーブルをスキャン（フルテーブルスキャン）する必要があり、これはO(n)の時間がかかります。一方、インデックスを使用すると、二分探索のようにO(log n)の時間で目的のレコードに到達できます。
具体的には、インデックスは指定したカラムの値をソートした形で別途保存し、各値に対して元のテーブルのどの位置にデータがあるかを示すポインタを持ちます。これにより、条件に合致するデータの位置を二分探索的に素早く特定できるのです。
参考記事
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);
ソート済みの配列に新しい値を挿入する位置を二分探索で見つけてください。
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 のループの中で探索を続けます
値が見つからない場合は、以下のどちらかの処理を毎回行います：
arr[mid] の場合：low = mid + 1 （右側を探索）arr[mid] > target の場合：high = mid - 1 （左側を探索）
最終的に探索範囲が狭まり続け、値が見つからない場合は以下のようになります：
low = mid + 1 となり、low > high になりますhigh = mid - 1 となり、同様に low > high になります具体例で見てみましょう。配列 [1, 3, 5, 7, 9] で値 6 を探す場合：
low = 0, high = 4, mid = 2 → arr[2] = 5 なので low = 3low = 3, high = 4, mid = 3 → arr[3] = 7 > 6 なので high = 2
ここで low = 3, high = 2 となり、low > high なのでループを抜けます
この時の low の値は、ちょうど「targetより小さい最後の要素の次の位置」を指しており、これが適切な挿入位置になります。これは「6」の場合、「5」と「7」の間に入るべき位置なので、インデックス3が正しい挿入位置になります。
元々ソートされていた配列が何回か回転された後の配列の最小値を二分探索で見つけてください。
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
# 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. もし中央値
#
# 例: [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
# 次の状態: left=4, right=5, mid=4, arr[mid]=0, arr[right]=1
# 0
# 最後の状態: left=4, right=4 (ループ終了)
# 結果: arr[left] = arr[4] = 0
山型の配列（最初は増加し、ある点から減少する）のピーク要素のインデックスを二分探索で見つけてください。
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
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]
# 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
# 次の状態: left=2, right=3, mid=2, arr[mid]=5, arr[mid+1]=7
# 5
# 最後の状態: left=3, right=3 (ループ終了)
# 結果: arr[left] = arr[3] = 7（これがピーク値）
アルゴリズムを学ぶ中で、二分探索とデータベースのインデックスに共通する考え方があることを知り、とても興味深く感じました。単純な仕組みでありながら、大きなパフォーマンス向上をもたらす二分探索の原理は、エンジニアとして知っておくべき基本だと実感しています。
今後もAtCoderで水色を目指して学習を続け、業務でもパフォーマンスを意識したコードが書けるようになりたいです。次は動的計画法や探索アルゴリズムについても学んでいく予定です。
この記事が同じようにアルゴリズムを学び始めた方の参考になれば嬉しいです。
株式会社シンシアでは、実務未経験のエンジニアの方や学生エンジニアインターンを採用し一緒に働いています。
※ シンシアにおける働き方の様子はこちら
弊社には年間100人程度の実務未経験の方に応募いただき、技術面接を実施しております。
この記事が少しでも学びになったという方は、ぜひ wantedly のストーリーもご覧いただけるととても嬉しいです！
Be the first to comment
