이분 탐색 (Binary Search)

목표

• Binary Search에 대해 설명할 수 있다.
• Binary Search 과정에 대해 설명할 수 있다.
• Binary Search를 Python으로 구현할 수 있다.
• Binary Search의 특징을 이해하여 시간 복잡도와 공간 복잡도를 계산할 수 있다.

요약

• 탐색 범위를 두 부분으로 분할하면서 찾는 방식
• 처음부터 끝까지 순회하면서 탐색하는 것보다 훨씬 빠르다.
  • 전체 탐색 : O(N), 이분 탐색 : O(logN)

과정

1. 우선 주어진 배열을 정렬해야 한다.
2. left, right로 mid 값을 구한다.
3. mid와 내가 구하고자 하는 값과 비교하여 구할 값이 mid보다 높으면 left를 mid + 1로 설정한다.
4. 구할 값이 mid보다 낮으면 right를 mid - 1로 설정한다.
5. mid와 구할 값이 일치하면 종료한다.

Python 코드

def binary_search(lst, goal):
    lst.sort()
    left, right = 0, len(lst) - 1

    while left < right:
        mid = (left + right) // 2
        if lst[mid] > goal:
            right = mid - 1
        elif lst[mid] < goal:
            left = mid + 1
        else:
            break


print(binary_search([4, 3, 6, 2, 8, 1, 9, 5, 7], 6))

시간 복잡도

• 시간 복잡도는 O(logN)이다.

공간 복잡도

기존에 주어진 배열에서 이루어지므로 공간 복잡도는 O(n)이다.

특징

장점

1. 빠른 탐색

Reference

• https://wootool.tistory.com/62
• https://github.com/gyoogle/tech-interview-for-developer/blob/master/Algorithm/Binary%20Search.md