Pythonでソート済み配列から要素の最初と最後の出現位置を検索する方法

昇順にソートされた整数型配列 A が与えられているとします。この中から、指定したターゲット値が出現する開始位置と終了位置を見つける必要があります。ターゲット値が配列内に存在しない場合は [-1, -1] を返します。

例えば、配列が [2,2,2,3,4,4,4,4,5,5,6]、ターゲット値が 4 である場合、値 4 はインデックス 4 〜 7 に出現するため、出力は [4, 7] となります。

解法のアプローチ：二分探索を2回行う

この問題は、二分探索（バイナリサーチ）を2回実行することで O(log n) の計算量で効率的に解けます。1回目の探索で左端（最初の出現位置）を特定し、2回目の探索で右端（最後の出現位置）を特定します。

手順の詳細

• はじめに res := [-1, -1] と初期化し、low := 0、high := 配列 A の長さと設定します。
• 1回目の探索（左端の検出）：low < high の間、以下を繰り返します。
  • mid := low + (high − low) / 2 を計算します。
  • A[mid] がターゲット値と等しい場合：high := mid として探索範囲を左側に狭めつつ、res[0] := mid、res[1] := mid を記録します。
  • A[mid] がターゲット値より小さい場合：low := mid + 1。そうでなければ high := mid。
• res[0] がまだ -1 の場合（ターゲットが見つからなかった場合）、そのまま res を返します。
• low := res[0] + 1、high := 配列の長さ に再設定します。
• 2回目の探索（右端の検出）：low < high の間、以下を繰り返します。
  • mid := low + (high − low) / 2 を計算します。
  • A[mid] がターゲット値と等しい場合：low := mid + 1 として探索範囲を右側に広げつつ、res[1] := mid を更新します。
  • A[mid] がターゲット値より小さい場合：low := mid + 1。そうでなければ high := mid。
• 最後に res を返します。

Pythonでの実装例

理解を深めるために、以下の実装例をご覧ください。

class Solution(object):
    def searchRange(self, nums, target):
        res = [-1, -1]
        low = 0
        high = len(nums)
        # 1回目の二分探索：最初の出現位置を探す
        while low < high:
            mid = int(low + (high - low) // 2)
            if nums[mid] == target:
                high = mid
                res[0] = mid
                res[1] = mid
            elif nums[mid] < target:
                low = mid + 1
            else:
                high = mid
        # 見つからなければそのまま返す
        if res[0] == -1:
            return res
        low = res[0] + 1
        high = len(nums)
        # 2回目の二分探索：最後の出現位置を探す
        while low < high:
            mid = int(low + (high - low) // 2)
            if nums[mid] == target:
                low = mid + 1
                res[1] = mid
            elif nums[mid] < target:
                low = mid + 1
            else:
                high = mid
        return res

ob1 = Solution()
print(ob1.searchRange([2,2,2,3,3,4,4,4,4,5,5,6], 4))

入力

[2,2,2,3,3,4,4,4,4,5,5,6]
4

出力

[5, 8]

この入力例では、値 4 はインデックス 5 から 8 まで連続して出現しているため、結果として [5, 8] が得られます。線形探索を使えば O(n) かかるところを、二分探索により O(log n) で高速に求解できるのがこの手法の大きな利点です。