[알고리즘 공부] 이진 탐색

이진 탐색 (Binary Search)

 

 이번에도 <이코테> 내용을 바탕으로 "이진 탐색" 알고리즘에 대해서 알아보도록 하겠습니다. 먼저 이진 탐색은 정렬된 배열에서 특정 요소의 위치를 효율적으로 찾는 검색 알고리즘입니다. 기본 원리는 대상 값을 중앙 값과 비교하여 탐색 범위를 반으로 줄여나가는 것입니다. 일단은 이진 탐색을 본격적으로 알기 이전에 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 순차 탐색(Sequential Search)과 코드를 비교하면서 살펴보도록 하겠습니다. 

 

 순차 탐색은 말 그대로 순차로 데이터를 탐색한다는 의미입니다. 리스트 안에 데이터를 하나씩 방문하면서 특정한 문자열과 같은지 검사하므로 구현에 있어서도 비교적 쉬운 편입니다. 순차 탐색에 대한 간단한 코드 예제는 아래와 같습니다. 

def sequential_search(arr, x):
    for i in range(len(arr)):
        if arr[i] == x:
            return i  # 원하는 값 x를 찾으면 그 위치를 반환
    return -1  # x를 찾지 못하면 -1 반환

# 예제 사용
arr = [1, 4, 2, 5, 3]
x = 5
result = sequential_search(arr, x)
if result != -1:
    print(f"원소 {x}는 배열의 {result}번째 인덱스에 있습니다.")
else:
    print(f"원소 {x}는 배열에 없습니다.")

 

 

 이진 탐색은 정렬된 배열에서 중간 값을 기준으로 탐색 범위를 반으로 줄여가며 원하는 값을 찾는 방법입니다. 이진 탐색에 대한 간단한 코드 예제는 아래와 같습니다. 

def binary_search(arr, x):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == x:
            return mid  # 원하는 값 x를 찾으면 그 위치를 반환
        elif arr[mid] < x:
            low = mid + 1
        else:
            high = mid - 1
    return -1  # x를 찾지 못하면 -1 반환

# 예제 사용
arr = [1, 2, 3, 4, 5]  # 이진 탐색을 위해서는 배열이 정렬되어 있어야 합니다.
x = 3
result = binary_search(arr, x)
if result != -1:
    print(f"원소 {x}는 배열의 {result}번째 인덱스에 있습니다.")
else:
    print(f"원소 {x}는 배열에 없습니다.")

 

 

두 코드를 살펴보면 다음과 같은 차이점이 있다는 것을 확인할 수 있습니다. 

 

1. 탐색 방식 

• 순차 탐색 : 배열의 처음부터 끝까지 순차적으로 탐색하여 원하는 값을 찾습니다. 배열이 정렬되어 있지 않아도 사용할 수 있습니다. 
• 이진 탐색 : 정렬된 배열에서만 사용할 수 있으며, 배열의 중간 값을 기준으로 탐색 범위를 반으로 줄여가며 값을 찾습니다. 

2. 시간 복잡도 

• 순차 탐색 : 최악의 경우 모든 요소를 확인해야 함으로 시간 복잡도는 O(n)입니다.
• 이진 탐색 : 탐색 범위를 매 단계마다 반으로 줄이므로 시간 복잡도는 O(logn)입니다.

3. 사용 조건

• 순차 탐색 : 정렬되지 않은 배열에서 사용할 수 있습니다.
• 이진 탐색 : 배열이 미리 정렬되어 있어야 사용할 수 있습니다. 정렬되지 않은 배열에 이진 탐색을 적용하려면 먼저 정렬 과정이 필요합니다. 

4. 코드 구현

• 순차 탐색 : 단순 반복문으로 구현
• 이진 탐색 : 반복문 또는 재귀를 통해 구현 가능, 중간 값을 기준으로 탐색 범위 조정

 

---

 

마무리

 이번에는 아주 간단하게 순차 탐색과 이진 탐색에 대해서 비교하고 코드를 살펴보았습니다. 아직도 알고리즘을 알아가려면 여러 가지 추가해야되는 상황이 많지만, 천천히 그리고 정확하게 보는 연습을 통해 나아가고자합니다. 그러다 보면 모든 문제는 아니겠지만 기초가 탄탄하니 어려운 문제들을 차분히 풀어 나갈 수 있는 날이 오겠지요? 그런 날일 기대하면서... 이번 글은 여기서 마치도록 하겠습니다. 

 

 

참 고

2023.12.08 - [IT/관련 정보] - [코딩 테스트] 이것이 취업을 위한 코딩테스트다 with 파이썬

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