[Algorithm] 이진 탐색

이번엔 코딩 테스트에서 자주 출제 되는 이진 탐색에 대해서 개념과 함께 코드에 대해서도 알아보도록 하겠습니다.

1. 탐색이란?

프로그래밍에서 탐색이 필요한 이유

탐색은 방대한 데이터 중에서 내가 필요로 하는 데이터를 찾는 행위입니다. 그런데 이 탐색이 왜 프로그래밍에서 필요할까요?
그 이유는 컴퓨터 프로그램은 대부분 데이터에 기반해서 작동을 하며, 이 데이터에서 사용자가 필요로 하는 데이터를 찾는 작업이 필수적이기 때문입니다. 예를 들면 다음과 같습니다.

• 데이터베이스에서 특정 회원의 정보를 찾아야 한다.
• 웹 페이지에서 특정 회원의 정보를 찾아야 한다.
• 게임에서 플레이어의 위치나 아이템을 찾아야 한다.
• AI 모델에서 최적의 값을 찾거나, 패턴을 탐색해야 한다.

이처럼 필요한 정보를 즉시 찾아낼 수 있어야 프로그램이 제대로 동작하게 됩니다.

탐색의 중요성

탐색은 단순히 데이터를 찾는 행위를 넘어서, 소프트웨어의 성능, 효율성, 사용자 경험에 영향을 줍니다.

1. 시간 복잡도의 핵심
   • 탐색 알고리즘은 보통 시간 복잡도로 성능이 평가됩니다.
   • 데이터가 커질수록 탐색 방법의 차이가 성능 차이로 직결됩니다.
2. 데이터 구조와 함께 발전
   • 탐색 알고리즘은 데이터 구조(배열, 해시 테이블, 트리, 그래프 등)와 맞물려 발전했습니다.
   • 좋은 데이터 구조 없이는 효율적인 탐색이 불가능하고, 탐색 알고리즘 없이는 데이터 구조를 활용할 수 없습니다.
3. 응용 분야의 다양성
   • 데이터베이스의 쿼리 처리
   • 웹 검색 엔진
   • 파일 시스템의 파일 탐색
   • 네트워크 라우팅 경로 탐색
   • AI 문제 (최적의 해 탐색)
4. 사용자 경험과 직결
   • 사용자가 “검색” 버튼을 눌렀을 때 빠르게 결과가 나오는 것이 바로 탐색 알고리즘 덕분입니다.
   • 지연이 길어지면 서비스 품질이 떨어집니다.

2. 순차 탐색

우리가 공부할 이진 탐색 전에 알아볼 가장 간단한 탐색 방법은 순차 탐색으로 배열이나 리스트와 같은 선형 자료 구조 안에 있는 모든 데이터들을 하나씩 차례대로 확인하는 방법입니다. 보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용됩니다. 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 데이터를 찾을 수 있다는 장점이 있습니다.
예제 코드를 통해서 알아보도록 하겠습니다.

# 순차 탐색 소스코드 구현
def sequential_search(n, target, array):
    # 각 원소를 하나씩 확인하며
    for i in range(n):
        # 현재의 원소가 찾고자 하는 원소와 동일한 경우
        if array[i] == target:
            return i+1

print("생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요.")

input_data = input().split()
n = int(input_data[0]) # 원소의 개수
target = input_data[1] # 찾고자 하는 문자열

print("앞서 적은 원소 개수만큼 문자열을 입력하세요. 구분은 띄어쓰기 한 칸으로 합니다.")
array = input().split()

# 순차 탐색 수행 결과 출력
print(sequential_search(n, target, array))

위 코드는 리스트에 들어갈 원소의 개수와 함께 찾고자 하는 문자열을 입력으로 받습니다. 그리고 그 이후에는 리스트에 들어갈 원소들을 입력 받아 리스트에 넣어주고 순차 탐색을 진행하는 sequential_search 함수를 통해 리스트에서 찾고자 하는 문자열이 등장하면 해당 인덱스를 반환하는 코드입니다.

3. 이진 탐색

이제 본론인 이진 탐색에 대해서 공부해봅시다. 이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘입니다. 데이터가 무작위일 때는 사용할 수 없지만, 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있다는 특징이 있습니다. 그래서 이진 탐색을 적용하고자 할 때에는 무조건 정렬이 선행되어야 합니다. 이진 탐색은 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 특징이 있습니다.

이진 탐색은 위치를 나타내는 변수 3개를 사용하는데 탐색하고자 하는 범위의 시작점, 끝점, 중간점을 사용합니다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색 과정입니다. 다음 이미 정렬된 10 개의 데이터 중에서 값이 4인 원소를 찾는 예시를 살펴보겠습니다.

이진 탐색 과정

• 리스트 : list = [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]
• 찾고자 하는 값 : 4

Step 1.

• 시작점 : 0
• 끝점 : 9
• 중간점 계산 : (시작점 + 끝점) // 2 -> (0+9) // 2 = 4
• 중간값 : 리스트의 4번째 요소의 값이므로 8
• 비교 : 4 < 8 이므로, 오른쪽 범위를 줄여야 합니다. 그러므로 끝점 업데이트를 진행합니다.
• 끝점 업데이트 : 끝점을 중간점에서 1을 뺀 값으로 업데이트 해서 다음 과정을 진행합니다.

Step 2.

• 시작점 : 0
• 끝점 : 3
• 중간점 계산 : (0+3) // 2 = 1
• 중간값 : list[1] = 2
• 비교 : 4 > 1 이므로, 왼쪼 범위를 줄여야 합니다. 그러므로 시작점 업데이트를 진행합니다.
• 시작점 업데이트 : 시작점을 중간점에서 1을 더한 값으로 업데이트 해서 다음 과정을 진행합니다.

Step 3.

• 시작점 : 2
• 끝점 : 3
• 중간점 계산 : (2+3) // 2 = 2
• 중간값 : list[2] = 4
• 비교 : 4 == 4 이므로 탐색 완료

전체 데이터의 개수는 10개이지만, 이진 탐색을 이용해 총 3번의 탐색으로 원소를 찾을 수 있었습니다. 이진 탐색은 한 번 확인할 때마다 확인하는 원소의 개수가 절반씩 줄어든다는 점에서 시간 복잡도가 $O(\log_{2} N)$입니다. 절반씩 데이터를 줄어들도록 만든다는 점은 앞서 다룬 퀵 정렬과 공통점이 있습니다.
이진 탐색을 구현하는 방법에는 2가지가 있는데 하나는 재귀 함수를 이용하는 방법이고, 다른 하나는 단순하게 반복문을 이용하는 방법입니다. 먼저 재귀 함수를 이용한 코드를 보도록 하겠습니다.

"""
10 7
1 3 5 7 9 11 13 15 17 19
4
"""

import sys

#이진 탐색 소스코드 구현(재귀 함수)
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 = map(int, input().split())
array = list(map(int, sys.stdin.readline().rstrip().split()))

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

다음은 단순하게 반복문을 사용한 코드입니다. 실행 결과는 재귀 함수와 같습니다.

"""
10 7
1 3 5 7 9 11 13 15 17 19
4
"""

# 이진 탐색 소스코드 구현(반복문)
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
    
    # 만약 start 값이 end 값보다 커지게 되면 찾고자 하는 원소가 없다는 것이므로 None 반환
    return None

# n(원소의 개수)과 target(찾고자 하는 문자열)을 입력받기
n, target = 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)

마치며

코딩 테스트 공부를 위해 공부한 내용을 블로그에 올리는 형식으로 공부를 하고 있어 코딩 테스트 문제로 자주 출제되는 이진 탐색에 대해서 알아보고 포스트를 작성해보았습니다. 특히 이번엔 정렬이 된 요소들에 대한 이진 탐색 방법에 대해서 알아 보았습니다.
정렬되지 않은 이진 탐색의 경우 트리를 이용해야 하지만 코딩 테스트에서는 트리를 이용한 문제의 출제 빈도는 잦지 않아 단순히 정렬된 요소들에 대한 이진 탐색만 알아보았습니다.
다음에 시간이 된다면 C 를 이용한 트리와 함께 이진 탐색 구현에 대해서도 알아보고자 합니다.

긴 글 읽어주셔서 감사드리며 오타나 잘못된 내용이 있다면 댓글 달아주시기 바랍니다 감사합니다!