[자료구조&알고리즘 | WEEK02] 이분 탐색(binary search)

이분 탐색(binary search)란?

---

이분탐색(binary search)은 정렬되어 있는 배열에서 특정 데이터를 찾기 위해 모든 데이터를 순차적으로 확인하는 대신 탐색 범위를 절반으로 줄여가며 찾는 탐색 방법이다.

이분탐색을 사용하는 이유와 시간 복잡도

내가 원하는 값을 빠르게 찾을 수 있기때문에!
정렬된 데이터에서만 사용 가능한 제약사항이 존재하지만 선형 검색과는 달리, 이진 검색에서는 주목할 원소를 다음에 검색할 범위의 중간 지점으로 단숨에 이동하게 된다. 일반적으로 n개의 원소가 오름차순으로 정렬된 배열에서 이진 검색에서 한 단계씩 진행할 때마다 검색 범위는 거의 반으로 좁혀진다.
따라서 시간 복잡도는 O(logN) 으로 굉장히 빠르다. 아래 그림에서 차이를 확인해보자.

 

선형탐색 vs 이분탐색 - 시간 복잡도 차이

 

이진 탐색 vs 선형 검색

 

알고리즘 종류	시간 복잡도
선형탐색	O(n)
이분탐색	O(logN)

 

이분탐색 알고리즘 방식

처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식이다.
처음 선택한 중앙 값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다.

말이 생각보다 어려운 것 같은데 그렇게 어렵지 않다.

 

예를 들어, 아래 이미지에서 우리가 찾는 값은 7(key)이다. 처음 중앙 값을 잡기 위해 맨 앞의 인덱스 0과, 맨 뒤의 인덱스 16를 기준으로 중앙 값은 (0 + 16) / 2 = 8(index)이다. 이때 중앙 값(8)보다 우리가 찾는 key 값은 왼쪽에 존재하게 된다. 그럼 중앙 값을 포함한 오른쪽의 값은 볼 필요가 없어졌다. 그럼 맨 앞의 인덱스 0과, 앞에서 임의로 정한 중앙 값 위치 (8 - 1) = 7(index) 값을 이제 제일 끝 값으로 지정한 후, 여기서 다시 중앙 값을 잡게 된다. 이런식으로 계속 반복/진행하다 우리가 찾아야 할 key값과 중앙 값이 일치하게 되면 값을 찾을 수 있다.

 

우리가 찾는 7 값을 찾기 위해 값이 어떻게 변하는지 보자.
편의상 맨 앞, 맨 끝, 중앙의 인덱스를 각각 left, right, mid로 부른다.

# 1 번째 - left: 0, right: 16, mid: 8
# 2 번째 - left: 0, right: 7, mid: 3
# 3 번째 - left: 4, right: 7, mid: 5
# 4 번째 - left: 4, right: 4, mid: 4 (정답)

 

아래 그림에서 화살표는 중앙 값이 어떻게 움직이는지 표현되어 있다.

 

조금 더 자세히 알아보기

n개의 원소가 오름차순으로 정렬된 배열 a가 있을 때
검색 범위의 맨 앞, 맨 끝, 중앙의 인덱스를 각각 left, right, mid로 초기화를 진행한다.

검색을 시작하기 전 초기화하는 과정은 다음 코드와 같다.

# 이진 탐색 전 초기화 작업
key = 7

def binary_search(arr, key):
    left = 0                            # 0
    right = n - 1(배열의 마지막 인덱스)   # 16

    # 중앙 값은 key 값을 찾을 때까지 계속 기준점이 바뀌고 업데이트를 해야하므로 반목문 안에 넣는다.
    while True: 
        mid = (left + right) // 2 (중앙 값)      # 8
    ...

 

위의 사진에서 0번째 인덱스를 left 변수에 대입, 16번째 인덱스를 right 변수에 대입, 중앙 값 mid는 (0 + 16) // 2 = 8이다.

 

임의로 지정한 중앙 값을 기준으로 우리가 찾는 값(key)가 나올 때까지 왼쪽, 오른쪽을 기준으로 값이 어디 있을지 판단하게 된다. 이러한 방식에서는 아래와 같이 총 3가지의 케이스가 나온다.

• 임의로 지정한 중앙 값이 우리가 찾는 key 값보다 작을 때 | a[mid] < key
  • 오름차순으로 정렬되어 있기 때문에 임의로 지정한 중앙 값 이하는 모두 볼 필요가 없다.
  • 즉, 중앙 값 기준으로 왼쪽의 값들은 모두 버리고, left 값을 중앙 값(mid) + 1 만큼 이동시킨다.
  • 이를 코드로 나타내면 다음과 같다.

def binary_search(arr, key):
    ...
    while True:
        mid = (left + right) // 2
        if a[mid] < key:
            # left 이전의 값들은 체크할 필요가 없으니, left 값을 중앙 값 이후로 옮기기
            left = mid + 1

• 임의로 지정한 중앙 값이 우리가 찾는 key 값보다 클 때 | a[mid] > key
  • 마찮가지로 임의로 지정한 중앙 값이 우리가 찾는 값보다 크다면, 오른쪽의 값들은 중앙 값보다 크기 때문에 중앙 값보다 오른쪽에 위치한 값들은 모두 볼 필요가 없어졌다.
  • 즉, 중앙 값을 기준으로 오른쪽 값들은 모두 버리고, right 값을 중앙 값(mid) - 1 만큼 이동시킨다.
  • 이를 코드로 나타내면 다음과 같다.

def binary_search(arr, key):
    ...
    while True:
        mid = (left + right) // 2
        if a[mid] > key:
            # left 이전의 값들은 체크할 필요가 없으니, pl 값을 중앙 값 이후로 옮기기
            right = mid - 1

• 중앙 값이 찾는 값과 동일해졌을 때
  • 전체 값에서 반씩 범위를 줄이다보니 드디어 우리가 찾는 값이 나왔다.
  • 이를 코드로 나타내면 다음과 같다.

def binary_search(arr, key):
    ...
    while True:
        mid = (left + right) // 2
        if a[mid] == key:
            return mid 	# key 값이 위치한 인덱스를 반환

 

💡

위에서 정의한 내용을 요약하면 아래와 같다.

1. a[mid] < key: 중앙(pc)에서 오른쪽으로 한 칸 이동하여 새로운 왼쪽 끝 left로 지정하고, 검색 범위를 뒤쪽 절반으로 좁힌다.

2. a[mid] > key: 중앙(pc)에서 왼쪽으로 한 칸 이동하여 새로운 오른쪽 끝 right로 지정하고, 검색 범위를 앞쪽 절반으로 좁힌다.

 

검색할 배열에서 값이 존재하지 않을 때

그런데 우리가 검색할 배열에서 값이 존재하지 않을 수도 있다.
값이 존재하지 않는지 어떻게 찾을 수 있을까?
답은 왼쪽의 기준을 담당하던 left 값이 오른쪽의 기준을 담당하는 right의 값보다 커지면 된다.
왼쪽과 오른쪽을 지나쳤는데도 답을 못찾았은 것이므로!

따라서 종료 조건은 다음 조건 중에 하나만 성립하면 된다.

 

💡

이진 검색의 종료 조건

1. a[mid]와 key가 일치하는 경우

2. 검색 범위가 더 이상 없는 경우

 

 

아래 사진은 '24' 값을 찾는데 값이 없을 경우를 나타낸 그림이다.

 

 

이분탐색 구현하기 | [비재귀적, 재귀적]

---

비재귀적으로 구현하기

# 이진 검색 알고리즘

from typing import Any, Sequence


def bin_search(a: Sequence, key: Any) -> int:
    """시퀸스 a에서 key와 일치하는 원소를 이진 검색"""
    left = 0              	# 검색 범위 맨 앞 원소의 인덱스
    right = len(a) - 1    	# 검색 범위 맨 끝 원소의 인덱스

    while left <= right:
        mid = (left + right) // 2  # 중앙 원소의 인덱스

        if a[mid] == key:
            return mid       # 검색 성공
        elif a[mid] < key:
            left = mid + 1   # 검색 범위를 뒤쪽 절반으로 좁힘
        else:
            right = mid - 1  # 검색 범위를 앞쪽 절반으로 좁힘

    return -1            	 # 검색 실패


# main 실행
if __name__ == '__main__':
    num = int(input('원소 수를 입력하세요.: '))
    x = [None] * num         # 원소 수가 num인 배열을 생성

    print('배열 데이터를 오름차순으로 입력하세요.')

    x[0] = int(input('x[0]: '))

    for i in range(1, num):
        while True:
            x[i] = int(input(f'x[{i}]: '))
            # 바로 직전에 입력한 원솟값보다 큰 값을 입력
            if x[i] >= x[i - 1]:	 
                break

    ky = int(input('검색할 값을 입력하세요.: '))        # 검색할 키 값 ky를 입력

    idx = bin_search(x, ky)                            # ky 갑과 같은 원소를 x에서 검색

    if idx == -1:
        print('검색 값을 갖는 원소가 존재하지 않습니다.')
    else:
        print(f'검색 값은 x[{idx}]에 있습니다.')

 

재귀적으로 구현하기

def binarySearch(array, value, left, right):
	if left > right:
		return False
	mid = (left + right) / 2
	if array[mid] > value:
		return binarySearch(array, value, left, mid-1)
	elif array[mid] < value:
		return binarySearch(array, value, mid+1, right)
	else:
		return mid

 

---

Ref

 

두잇파이썬

위키백과 - binarySearch