アルゴリズムの二分探索を理解した

解いた問題

LeetCode 35. Search Insert Position
昇順に並んだ重複なし整数配列numsと整数targetが与えられて、targetと値が等しいnumsのインデックスを返し、等しい値がない場合はtargetが昇順だとどこに入るかのインデックスを返すという問題

最初に考えた解法

昨日学んだ２ポインタ法が使えそうだと思い実装。

search_insert_position_tp.py

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        if not nums:
            return 0
        
        k = 0
        for i in range(len(nums)):
            if nums[i] == target:
                return i
            else:
                if nums[i] < target:
                    k += 1
                else:
                    return k
        return k

上記で正解。
はじめて1回目の試行で正解したので気持ちよくなっていたら、問題文に「$O(log_n)$でといてね」という条件があることに気づいた。

２ポインタ法はO(n)だからもっと早い方法があるのか...とぬか喜びした気分になった。

二分探索

よく聞くアルゴリズム。
探索範囲を半分に割っていくことで比較の回数をうんと抑えることが可能。

search_insert_position_binary_search.py

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)-1 # indexを見たいからlen-1

        while left <= right: # leftとrightが反転するまで繰り返す
            mid = (left + right) // 2 # 半分に割った個所で比較
            if nums[mid] == target:
                return mid
            elif nums[mid] < target: # midの値よりtargetのほうが大きいならmidより左を見る必要がない
                left = mid + 1
            else:
                right = mid - 1 # 同じく右を見る必要がない
        return left # 等しい値がない場合はleftが挿入位置になる

この終了条件はk回分割された後の残りが1以下になっていることなので、
$n/2^k \leq 1$ ⇔ $k \geq log_2 n$
と計算できるからオーダーとしては$O(logn)$になる。

違和感としてleftをreturnしたら想定の一個後ろにtargetが挿入されちゃうんじゃ？と思ったが、whileの中でleft = mid + 1してからreturnしているため、「targetより小さい数の一個次」をleftがさしているのでleftを返却が正しそう。

感想

これはアルゴリズム解く中の1つの手段として多々使いそう。

ただ実務でどう使うのか想像がついていない。
調べたところ日付でパーディションが並ぶテーブルから最初に条件を満たす日を高速に見つけるために使ったりするそう。

やればやるほど知っていて当たり前、ふとした時にさらっと使うのがアルゴリズムな気がしてきた。

あとオーダー記法のlogはeかと思っていたが、何でもいいと知って面白かった。
定数倍になるから確かに何でもいいね。面白いね。