항해99 TIL 3주차 - 14

이진 검색

이진 검색이란 오름차순으로 정렬되어있는 배열에서 특정한 값을 찾아내는 알고리즘이다.
배열의 중간을 기준으로 찾으려는 중간의 값이 찾으려는 값보다 작을 경우 오른쪽으로 검색하고, 찾으려는 값보다 더 큰 경우 왼쪽을 검색한다.

이진 검색 장점

선형 탐색에 비해 비교적 빠르다는 장점이 있다.
선형 탐색의 시간복잡도는 0(n)이지만 이진 검색의 시간복잡도는 O(logn)이기 때문에 더 빠르다는것을 알 수 있다.

이진 검색 단점

정렬된 리스트에서만 사용할 수 있다는 단점이 있다.

이진 검색 구현 코드

def binary_search(nums, target):
    def bs(start, end):
        if start > end:
            return -1

        mid = (start + end) // 2

        if nums[mid] < target:
            return bs(mid + 1, end)
        elif nums[mid] > target:
            return bs(start, mid - 1)
        else:
            return mid

    return bs(0, len(nums) - 1)