이분 탐색 (Binary Search)

• 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다.
• 이분 탐색(Binary Search)의 이분은 '둘로 나눈다'는 뜻이다. 탐색할 자료를 둘로 나누어 찾는 값이 있을 법한 곳만 탐색한다.
• 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있다.
• 하지만 검색이 반복될 때마다 목표값을 찾을 확률이 두 배가 되므로 속도가 빠르다는 장점이 있다.

전개

1. 배열을 정렬한다.
2. 중간 위치를 찾는다.
3. 찾은 값과 중간 위치 값을 비교한다.
4. 같다면 원하는 값을 찾았으므로 위치 번호를 결괏값으로 돌려준다.
5. 찾는 값이 중간 위치 값보다 크다면 중간 위치의 오른쪽 배열을 대상으로 다시 탐색한다.(1번 과정부터 반복)
6. 찾는 값이 중간 위치 값보다 작다면 중간 위치의 왼쪽 배열을 대상으로 다시 탐색한다.(1번 과정부터 반복)

이미지 출처

시간 복잡도

• 이분 탐색은 값을 비교할 때마다 찾는 값이 있을 범위를 절반씩 좁혀나간다.
• 절반씩 좁혀나가는 과정이 있으므로 시간 복잡도는 O(${logN}$)이다.

구현 코드

def binary_search(numbers, target):
    """
    이분 탐색 알고리즘으로 특정 값을 찾는다.
    값이 있으면 값의 인덱스를 반환하고,
    값이 없으면 -1를 반환한다.
    """

    left = 0
    right = len(numbers) - 1

    while left <= right:
        mid = (left + right) // 2

        if target == numbers[mid]:
            return mid

        elif target > numbers[mid]:
            left = mid + 1

        else:
            right = mid - 1

    return -1


if __name__ == '__main__':
    numbers = [6, 5, 6, 4, 3, 2, 1]
    target = 3

    numbers.sort()
    target_idx = binary_search(numbers, target)

    print(numbers)
    print(target_idx)

'''
출력 결과

[1, 2, 3, 4, 5, 6, 6]
2
'''

Ref

• 모두의 알고리즘 with 파이썬 - 이승찬님