Leetcode 704. Binary Search

Problem

与えられた整数配列から特定の数値を探し出す問題で、Binary Search（二分探索）を用いることが求められています。

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

InputとOutputの例は次になります。

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

What's Binary Search

Interviewにおいてよく質問される内容とその解答例を示します。
Q1 : 二分探索の原理について説明してください。
A1 : 二分探索は、ソート済みの配列に対して特定の値を効率的に探すためのアルゴリズムです。このアルゴリズムは、配列の中央の要素を比較し、目標値が中央の要素よりも大きいか小さいかによって検索範囲を半分に減らしていくことで動作します。この過程を目標値を見つけるまで、または検索範囲がなくなるまで繰り返します。

Q2 : 二分探索の時間複雑度と空間複雑度について説明してください。
A2 : 二分探索の時間複雑度は O(log n) です。これは、各ステップで検索範囲が半分になるためです。空間複雑度は O(1) です。これは、追加のメモリを使用せずに配列内を移動するだけで二分探索を実行できるためです。

Q3 : 二分探索はどのようなシチュエーションで最も効果的ですか？
A3 : 二分探索は、大きなデータセットを持つソート済みの配列に対して、特定の値を高速に探す場合に最も効果的です。データセットの大きさに対して対数的な時間複雑度を持つため、データセットが大きくなるほどその効率性が増します。

Implementation

Pythonを使用した基本的な二分探索の実装を以下に示します。

def binarySearch(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

中間値を設定する際に、mid = left + (right - left) // 2としています。mid = (left + right) // 2としても基本的には問題ありません。ただし、大きな数値を扱う際には、left + rightが整数型の最大値を超えてオーバーフローを引き起こす可能性があります。

そのため、mid = left + (right - left) // 2 のように書くと、このオーバーフローの問題を防ぐことができます。これは、right - leftが必ず0以上であり、いかなる状況でも整数型の範囲を超えることが無いからです。

この問題は、特に大きな数値を扱うことが一般的な言語（例えばJavaやC++）でより重要となります。一方で、Pythonではこの問題はそれほど顕著ではありません。なぜなら、Pythonは動的な型付けが行われ、整数型のオーバーフローが自動的に長整数型に変換されるためです。ただし、他のプログラミング言語でも適用可能なコードを書くため、またはオーバーフローに対する一般的な理解を深めるためには、mid = left + (right - left) // 2 の形式を使っています。

また、境界値の条件にも気をつける必要があります。例えば、while left <= rightの =を忘れないようにする、 right = mid - 1の-1を忘れないようにするなどです。

参考 : 再帰を使った実装

Space complextityがO(n)と非効率になってしまいますが、再帰を使って書くことも可能です。

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        def binary_search_recursive(left, right):
            if right >= left:
                mid = left + (right - left) // 2
                if nums[mid] == target:
                    return mid
                elif nums[mid] > target:
                    return binary_search_recursive(left, mid-1)
                else:
                    return binary_search_recursive(mid+1, right)
            else:
                return -1
        return binary_search_recursive(0, len(nums) -1)

Reference