[이분 탐색] 알고리즘 설명 및 예제 풀이

이분 탐색(Binary Search)

이분 탐색은 코딩 테스트에 많이 출제되는 문제 중 하나입니다.

이분 탐색의 주요 조건은 정렬되어 있는 배열입니다.

 

순차탐색의 경우 배열의 처음부터 끝까지 배열의 모든 원소를 체크합니다.

이분탐색은 탐색 범위를 절반씩 줄여가며 찾아가는 탐색 방법입니다.

 

예를 들어보겠습니다.

[ 9, 4, 2, 5, 3, 8 ]

다음과 같은 리스트가 주어졌을 때 숫자 2를 찾는다고 가정해 보겠습니다.

 

이분탐색을 위해 먼저 정렬을 해줍니다.

[ 2, 3, 4, 5, 8, 9 ]

먼저 배열의 중간에 위치한 5와 2를 비교합니다.

2는 5보다 작으므로, 탐색 범위를 5의 왼쪽에 있는 원소들로 줄일 수 있습니다.

이제 탐색 범위는 [ 2, 3, 4 ]이 됩니다.

 

이번에는 중간 원소인 3과 2를 비교합니다.

2는 3보다 작으므로 3의 왼쪽에 위치한다는 것을 알 수 있습니다.

이제 탐색 범위는 [ 2 ]가 됩니다.

 

 

이분 탐색 - 파이썬(Python) 코드

def binarySearch(num_list):
    while num_list:
        mid = len(num_list) // 2
        if target == num_list[mid]:
            return True
        elif target < num_list[mid]:
            num_list = num_list[:mid]
        elif target > num_list[mid]:
            num_list = num_list[mid:]
    return False

num_list = [9,4,2,5,3,8]
num_list.sort()

target = 9
print(binarySearch(num_list))