LeetCode 704번 Binary Search

https://leetcode.com/problems/binary-search/description/

---

문제 파악

주어진 수에 목표 숫자가 있는지 확인하는 문제다.

접근 방법

리스트가 배열된 상황에서 중간 지점을 찾아 이보다 큰 지 작은지를 판단하는 이진탐색을 통해 해결할 수 있을 것 같다. 배열을 정렬된 상태에서 효율적으로 찾기 위해 이를 사용하고 문제에서 요구하는 시간복잡도도 만족할 것 같다.

코드 구현

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        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

가장 왼쪽 값과 가장 오른쪽 값을 정하고 이 중간 부분부터 쪼개가며 간단하게 반복문을 사용해서 풀었다.

from bisect import bisect_left

class Solution:
    def search(self, nums, target):
        idx = bisect_left(nums, target)
        if idx != len(nums) and nums[idx] == target:
            return idx
        
        return -1

강의에서 소개한 라이브러리를 통해서 풀어봤다. (해답 참고)

배우게 된 점

강의를 통해 파이썬은 라이브러리를 통해서 이진탐색을 일일히 구현하지 않아도 풀 수 있음을 알게되었다!