[탐색] 이진 탐색/이분 탐색(Binary Search) 개념 및 구현

가장 기본 탐색 방법인 순차 탐색에 대해 먼저 알아본 뒤, Python으로 이진 탐색을 구현하는 방법까지 살펴보자!

 

순차 탐색(Sequential Search)

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

• 순차 정렬은 보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용한다.
• 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 원소(데이터)를 찾을 수 있다.

 

동작 과정

초기 단계

다음 리스트 안에서 c를 찾아보자.

 

가장 먼저 첫 번째 데이터를 확인한다.

• `target`(=`c`)와 같지 않으므로 다음 데이터로 이동한다.

 

두 번째 데이터를 확인한다.

• `target`(=`c`)와 같지 않으므로 다음 데이터로 이동한다.

 

세 번째 데이터를 확인한다.

• `target`(=`c`)와 같으므로 탐색을 마친다.

 

Code

순차 탐색을 파이썬 코드로 작성하면 다음과 같다.

def sequential_search(n, target, array):
    for i in range(n):
        if array[i] == target:	# 현재의 원소가 찾고자 하는 원소와 동일한 경우
            return i


n = 5
array = ["java", "python", "c", "kotlin", "c++"]
target = "c"
print(sequential_search(n, target, array))

• 실행 결과

2

 

이처럼 순차 탐색은 데이터 정렬 여부와 상관없이 가장 앞에 있는 원소부터 하나씩 확인해야 한다.

 

데이터의 개수가 N개일 때 최대 N번의 비교 연산이 필요하므로, 순차 탐색의 최악의 경우 시간 복잡도는 `O(N)`이다.

 

이진 탐색(Binary Search)

배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다.

• 데이터가 이미 정렬되어 있는 상태라면 매우 빠르게 데이터를 찾을 수 있다.
• 이진 탐색은 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방식이다.
• 찾으려는 데이터와 중간점(시작점과 끝점의 중간) 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는다.
• 한 번 확인할 때마다 확인하려는 원소의 개수가 절반씩 줄어들기 때문에 시간 복잡도가 `O(logN)`이다.

 

동작 과정

초기 단계

• 다음 리스트에서 `4`를 찾아보자.

 

⚠️ 이진 탐색은 정렬되어 있는 상태일 때만 적용 가능하므로 오름차순으로 정렬해야 한다.

 

`시작점`과 `끝점`으로 `중간점` 값 설정

• 중간점이 실수일 때는 소수점 이하를 버린다. ➡️ `시작점`: 0, `끝점`: 9, `중간점`: 4

• `배열[중간점]` > `target`
  ➡️ `중간점` 이후의 값을 버리고, `끝점`을 `중간점 - 1`인 `3`으로 옮긴다.

 

다시 설정된 `배열[중간점]` 데이터와 `target`을 비교한다.

• `배열[중간점]` < `target`
  ➡️ `중간점` 이전의 값을 버리고, `시작점`을 `중간점 + 1`인 `2`으로 옮긴다.

다시 설정된 `배열[중간점]` 데이터와 `target`을 비교한다.

• `배열[중간점]` == `target` ➡️ 탐색 종료

💡 이진 탐색 과정 정리
0. 배열이 정렬되어 있지 않다면 정렬한다.
1. `시작점`과 `끝점`을 기준으로 `중간점`을 설정한다.
2. `배열[중간점]`과 `target` 값을 비교하여 `시작점` 및 `끝점`을 조정한다.
- `배열[중간점]` < `target`: `시작점` = `중간점` + 1
- `배열[중간점]` > `target`: `끝점` = `중간점` - 1
3. `시작점 <= 끝점`일 동안만 반복하며 `중간점 == 타겟값`일 경우 탐색을 종료한다.

 

Code1 - 재귀 함수 이용

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 = 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)

 

Code2 - 반복문 이용

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 = 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)

 

• 실행 결과

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

 

이진 탐색 연습하기

https://www.acmicpc.net/problemset?sort=ac_desc&algo=12 

문제 - 1 페이지

 

Reference

이것이 취업을 위한 코딩 테스트다 with 파이썬