[LeetCode] 704. Binary Search

1. 문제 이해

오름차순으로 정렬된 정수들의 배열이 주어진다.

target 정수의 배열 인덱스를 구한다.

시간복잡도 O(logn)으로 풀어야 한다.

 

 

2. 풀이 과정

시간복잡도 O(logn)이라는 조건이 있다.

Binary Search로 접근한다.

 

시작 인덱스, 끝 인덱스를 매개변수로 하는 재귀함수를 구현한다.

 

 

3. 전체 코드

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        #a는 시작 인덱스, b는 끝 인덱스
        def binary_search(a: int, b: int) -> int:
            if a > b:
                return -1

            mid = (a+b)//2
            if nums[mid] == target:
                return mid

            if nums[mid] > target:
                return binary_search(a, mid-1)
            elif nums[mid] < target:
                return binary_search(mid+1, b)
        
        ans = binary_search(0, len(nums)-1)
        return ans

 

Python의 bisect 모듈을 사용한다.(Binary Search를 지원한다.)

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        index = bisect.bisect_left(nums, target)

        if index < len(nums) and nums[index] == target:
            return index
        else:
            return -1

 

 

4. 생각할 점

- 재귀 함수는 항상 종료 조건을 고려해야 한다.

- Python의 bisect 모듈에는 Binary Search가 구현되어 있다.

 

 

5. 출처

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

- 박상길, 파이썬 알고리즘 인터뷰, 책만, 2020