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

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

問題

原文

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

よく目にする方の解答

解答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)