よわよわエンジニアが解く704. Binary Search

再帰処理を使わずに解いた例。
右のインデックスは配列の長さの−1
配列を分割する際に、halfは見たのでそれぞれ左右に1個ずらす。

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

再起処理を使って解いた例。終了条件が逆になるので注意。

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