[LeetCode][Python] 704. Binary Search

- 문제 링크: https://leetcode.com/problems/binary-search/

- 난이도: Easy

 

정렬된 숫자 배열이 주어지고, target을 찾아 인덱스를 반환한다.

기초적인 이분탐색 문제.

주의할 점은 l <= r 부분과 mid 계산 부분. 타 언어에서는 (l + r) / 2 처럼 쓰면 overflow가 날 수 있으니, 아래처럼 쓰는게 좋다

이 문제는 l == r 인 부분까지 체크해야 한다

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

        return -1