[알고리즘] 이진 탐색 / 이분 탐색 (Binary Search)

이진 탐색은 정렬된 리스트에 적용할 수 있는 간단한 고속 탐색 기법이며,

이분 탐색이라고도 불린다.

 

순차 탐색

리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법이다.

 

이진 탐색

정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.

• 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다.

 

이진 탐색 (이분 탐색) 알고리즘

• 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.
• 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다.
• 시작점, 끝점, 중간점(start, end, mid) 변수 3개를 사용하여 탐색한다.
• 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색의 과정이다.

 

이진 탐색 동작

반복문과 재귀 두 가지 방법을 사용할 수 있다.

 

1. 자료를 오름차순으로 정렬한다.
2. 자료의 중간값(mid)이 찾고자 하는 값(target)인지 비교한다.
3. mid 값이 target과 다르다면 대소관계를 비교하여 탐색 범위를 좁히고, target과 mid 값이 같을 때까지 아래 조건에 따라 2번과 3번을 반복한다.
   • target이 mid 값 보다 작으면 end를 mid 왼쪽 값으로 바꿔준다. (절반의 왼쪽 탐색)
   • target이 mid 값 보다 크면 start를 mid 오른쪽 값으로 바꿔준다. (절반의 오른쪽 탐색)

 

이진 탐색 동작 예시

이미 정렬된 10개의 데이터 중에서 값이 4인 원소를 찾는 예시를 살펴보자.

• [Step 1] 시작점: 0, 끝점: 9, 중간점: 4 (소수점 이하 제거)

• [Step 2] 시작점:0, 끝점: 3, 중간점: 1 (소수점 이하 제거)

• [Step 3] 시작점: 2, 끝점: 3, 중간점: 2 (소수점 이하 제거)

 

이진 탐색의 시간 복잡도

• 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 log₂𝑁에 비례한다.
• 예를 들어 초기 데이터 개수가 32개일 때, 이상적으로 1단계를 거치면 16개가량의 데이터만 남는다.
  • 2단계를 거치면 8개가량의 데이터만 남는다.
  • 3단계를 거치면 4개가량의 데이터만 남는다.
• 다시 말해 이진 탐색은 탐색 범위를 절반씩 줄이며, 시간 복잡도는 𝑂(log𝑁) 을 보장한다.

 

이진 탐색 소스코드 : 파이썬 (Python)

1. 재귀 함수로 구현한 이진 탐색

# 재귀 함수로 구현한 이진 탐색
def binary_search(array, target, start, end):
    if start > end:
        return None
        
    # 현재 범위에서 중간 값 찾기    
    mid = (start + end) // 2
    
    # 원하는 값을 찾은 경우 중간점 인덱스 반환
    if array[mid] == target:
        return mid
    # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인 (절반의 왼쪽 부분)
    elif array[mid] > target:
        return binary_search(array, target, start, mid-1)
    # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인 (절반의 오른쪽 부분)
    else:
        return binary_search(array, target, mid+1, end)


# n(원소의 개수)와 target(찾고자 하는 문자열)을 입력받기
n, target = list(map(int, input().split()))
# 전체 원소 입력받기
array = list(map(int, input().split()))

# 이진 탐색 수행 결과 출력
result = binary_search(array, target, 0, n-1)

if result == None:
    print("원소가 존재하지 않습니다")
else:
    print(result+1)

 

2. 반복문으로 구현한 이진 탐색

# 반복문으로 구현한 이진 탐색
def binary_search(array, target, start, end):

    while start <= end:
        mid = (start + end) // 2
        
        # 찾은 경우 중간점 인덱스 반환  
        if array[mid] == target:
            return mid
        # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
        elif array[mid] > target:
            end = mid - 1
        # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
        else:
            start = mid + 1
            
    return None


# n(원소의 개수)와 target(찾고자 하는 문자열)을 입력받기
n, target = list(map(int, input().split()))
# 전체 원소 입력받기
array = list(map(int, input().split()))

# 이진 탐색 수행 결과 출력
result = binary_search(array, target, 0, n-1)

if result == None:
    print("원소가 존재하지 않습니다")
else:
    print(result+1)

실행 결과

# sample input
# 10 7
# 1 3 5 7 9 11 13 15 17 19
>>> 4

# sample input
# 10 7
# 1 3 5 6 9 11 13 15 17 19
>>> 원소가 존재하지 않습니다

 

 

파이썬 (Python) 이진 탐색 라이브러리

Python에서는 bisect라는 이진 탐색 라이브러리(모듈)을 지원한다.

• bisect_left(a, x): 정렬된 순서를 유지하면서 배열 a에 데이터 x를 삽입할 가장 왼쪽 인덱스를 찾아 반환하는 메소드
• bisect_right(a, x): 정렬된 순서를 유지하면서 배열 a에 데이터 x를 삽입할 가장 오른쪽 인덱스를 찾아 반환하는 메소드

 

예제 1

from bisect import bisect_left, bisect_right

a = [1, 2, 4, 4, 8]
x = 4

print(bisect_left(a, x))
print(bisect_right(a, x))

실행 결과

>>> 2
# 리스트 a에 4를 삽입할 가장 왼쪽 인덱스는 2이다.

>>> 4
# 리스트 a에 4를 삽입할 가장 오른쪽 인덱스는 4이다.

 

예제 2

값이 특정 범위에 속하는 데이터 개수 구하기

from bisect import bisect_left, bisect_right

# '정렬된 리스트'에서 `값이 특정 범위에 속하는 원소의 개수`를 구할 때 좋다.
# 값이 [left_value, right_value]인 데이터의 개수를 반환하는 함수
def count_by_range(a, left_value, right_value):
    right_index = bisect_right(a, right_value)
    left_index = bisect_left(a, left_value)
    
    print('right : ', right_index)
    print('left :', left_index)
    
    return right_index - left_index


# 배열 선언
a = [1, 2, 3, 3, 3, 3, 4, 4, 8, 9]

# 값이 4인 데이터 개수 출력
print(count_by_range(a, 4, 4))
print(count_by_range(a, -1, 3))

실행 결과

>>> right :  8
>>> left : 6
>>> 2
# 리스트 a에 4는 총 2개 존재한다.

>>> right :  6
>>> left : 0
>>> 6
# 리스트 a에 -1~3사이의 값은 총 6개 존재한다.

 

이렇게, Python의 bisect라이브러리(모듈)은 '정렬된 리스트'에서 '값이 특정 범위에 속하는 원소의 개수'를 구할 때 사용하면 효율적이다.

 

파라메트릭 서치 (Parametric Search)

최적화 문제를 결정 문제 ('예' 혹은 '아니오') 로 바꾸어 해결하는 기법이다.

• 예시: 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제
• 일반적으로 코딩 테스트에서 파라메트릭 서치 문제는 이진 탐색을 이용하여 해결할 수 있다.

 

---

참고 자료

https://code-angie.tistory.com/3

https://freedeveloper.tistory.com/275?category=888096

https://velog.io/@kimdukbae/%EC%9D%B4%EB%B6%84-%ED%83%90%EC%83%89-%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-Binary-Search