【LeetCode】704. Binary Search 解答・解説【Python】

はじめに
問題
1. 原文
2. 内容
方針
解答
1. 解答1：iterative(繰り返し)
2. 解答2：recursive(再帰)
補足・参考・感想

はじめに

LeetCodeの問題を解答します。

なるべく、問題の和訳と詳細なコメントを書いています。

余裕があれば、複数のアプローチの解答と、実際の面接を想定して英語での解法やコメントを書いています。

様々なカテゴリの問題をランダムにあたる方法も良いですが、

二分探索、連結リストなど、テーマを絞って集中的に解いた方が練習しやすい方は以下の記事が有用です。

テーマごとに問題を分類しました。

LeeetCodeの問題をアルゴリズムとデータ構造による分類しました。

また、LeetCodeではAtcoderと違ってクラスと関数を定義して解答します。

LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめています。

はじめてLeetCodeに触れる方はこちらの記事も役に立つと思います。

解答前に知っておくと役に立つかもしれない情報

問題

原文

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.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

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

1
2
3

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

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2 Output: -1 Explanation: 2 does not exist in nums so return -1

1
2
3

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

Constraints:

1 <= nums.length <= 10⁴

-10⁴ < nums[i], target < 10⁴

All the integers in nums are unique.

nums is sorted in ascending order.

内容

昇順にソートされた整数配列numsと、整数targetが与えられます。

targetがnumsに含まれているか探索する関数を書いてください。

もし、targetが存在する場合は、そのインデックスを返し、そうでない場合は-1を返してください。

※正しくない可能性があります。

方針

・二分探索をそのまま実装する

解答

解答1：iterative(繰り返し)

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        min = 0
        max = len(nums) - 1
        while min <= max:
            middle = (min + max) // 2
            if target == nums[middle]:
                return middle
            elif target < nums[middle]:
                max = middle - 1
            else:
                min = middle + 1
        return -1

class Solution:

def search(self, nums: List[int], target: int) -> int:

min = 0

max = len(nums) - 1

while min <= max:

middle = (min + max) // 2

if target == nums[middle]:

return middle

elif target < nums[middle]:

max = middle - 1

else:

min = middle + 1

return -1

・配列numsの左端のインデックスをmin、右端のインデックスをmaxとして保持します。

・while文では、左側と右端のインデックスの位置が逆になるまで繰り返します。

探索対象の値を左右から範囲を絞りながら探すイメージです。

while文でループを繰り返す度に探索範囲が半分になります。

while文の中では、毎回左側と右側のインデックス平均を求め、中央のインデックスをmiddleとして取ります。

もし、探索対象の値が中央の要素と同じなら、その場所を示すインデックスmiddleを返します。

もし、探索対象の値が中央の要素よりも大きければ、左側のインデックスminを、中央のインデックスmiddle+1にして、探索範囲を半分にします。

もし、探索対象の値が中央の要素よりも小さければ、右側のインデックスmaxを、中央のインデックスmiddle-1にして、探索範囲を半分にします。

minとmaxは左右からだんだんと近づいていき、探索対象の値が無ければその位置関係が逆転します。

こうなった時、numsには探索対象の値がないので、return文で-1を返します。

解答2：recursive(再帰)

class Solution:
  def search(self, nums: List[int], target: int) -> int:
      start = 0
      end = len(nums) - 1
      return self.binary_search(nums, start, end, target)
  
  def binary_search(self, nums, start, end, target):
      if start > end:
          return -1
      middle = (start + end) // 2
      if target < nums[middle]:
          end = middle - 1
      elif target > nums[middle]:
          start = middle + 1
      else:
          return middle
      return self.binary_search(nums, start, end, target)

class Solution:

def search(self, nums: List[int], target: int) -> int:

start = 0

end = len(nums) - 1

return self.binary_search(nums, start, end, target)

def binary_search(self, nums, start, end, target):

if start > end:

return -1

middle = (start + end) // 2

if target < nums[middle]:

end = middle - 1

elif target > nums[middle]:

start = middle + 1

else:

return middle

return self.binary_search(nums, start, end, target)

時間・空間的なスコアはiterativeな解答よりも悪かった。

補足・参考・感想

参考

二分探索を再帰的に実装するコードは初めて見たので勉強になった。

再帰的なコードを書いたときの特徴やメリットデメリットは要確認

二分探索の実装

前：268. Missing Number

次：3. Longest Substring Without Repeating Characters

LeetCode 解答・解説記事一覧