[TIL] 05/28 항해99 20일차 - 이진탐색

 

들어가며

이진 탐색은 예전에 맛보기로 공부했던 적이 있었기도 하고 크게 어려운 개념이 아니라 이해하기 쉬웠다. 늘 말하듯이 구현은 다른 문제지만.

 

오늘의 TIL은 이진 탐색의 개념을 정리해보고자 한다!

 

---

이진 탐색

 

 

 

이진 탐색 알고리즘(binary search algorithm)은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다.
출처 - 위키백과

 

 

이진 탐색(Binary Search)은 그림에서 보는 것처럼 중앙값을 기준으로 절반 씩 줄여나가면서 목표값을 찾아가는 알고리즘이다. 단, 이진 탐색을 하기 위해서는 자료가 순서에 따라 정렬되어 있어야 한다. 만약 정렬되어 있지 않은 자료에서 이진 탐색을 한다고 하면, 중앙값 기준으로 좌/우가 무조건 작거나 크다고 보장할 수 없기 때문이다.

 

 

이진 탐색 알고리즘은 선형 탐색에 비해 매우 뛰어난 성능을 보여준다. 선형 탐색은 원하는 값을 처음부터 끝까지 모두 탐색해야하기 때문에 만약 찾으려는 값이 뒤쪽에 위치해있거나 아예 없으면 최악의 성능을 보여준다. 반면, 이진 탐색은 자료를 절반씩 나눠가면서 탐색하기 때문에 O(log n)의 시간복잡도를 갖게 된다.

 

 

 

이러한 이진 탐색을 쉽게 알고 싶다면 니꼬쌤의 영상을 참고하자!

 

 

 

이진 탐색 구현하기

재귀 구조

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)

 

중앙값이 찾으려는 값보다 작은 경우 즉, 찾으려는 값이 중앙값 오른쪽에 있는 경우에는 중앙을 기준으로 오른쪽 배열을 검색하고,

반대의 경우에는 왼쪽 배열을 검색하는 재귀 호출을 한다.

 

모든 검색이 끝나면 target과 nums[mid]가 같아지는 순간이 오게 되는데, 이때가 원하는 값을 찾았을 때이므로 해당 인덱스를 리턴해준다.

 

 

이 과정을 파이썬에서는 간단하게 모듈을 이용해서 해결할 수 있다.

 

내장 모듈 이용

import bisect

def binary_search_builtin(nums, target):
    idx = bisect.bisect_left(nums, target)

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

 

한눈에 봐도 역시 간단해보인다. 다만 여기에 조건문이 추가되는 이유는 찾으려는 값이 주어진 배열에 없을 때 bisect_left 함수는 -1이 아니라 0을 반환해준다. 이렇게 되면 0번째 인덱스에 있는 값이 내가 찾는 값인지 아닌지를 알아내야하는데, 이게 바로 위의 조건문이다.

 

이렇게 파이썬 모듈을 이용하여 간단하게 이진 탐색이 구현가능하다!

 

---

마치며

오늘 정말 한게 없다는게 TIL에서 보이네... 그래도 열심히 쌓인 피로를 풀었다는 것에 의의를 두기로 한다.

열심히 하는 것도 중요하지만 잘 쉬는 것도 중요하니까!

 

 

오늘의 한마디 by 상훈님 - 절대, 절대, 절대 포기하지 마라