이분 탐색 (Binary Search)

이분탐색 (Binary Search)

이분탐색은 정렬된 데이터에서 특정 값을 효율적으로 찾기 위한 알고리즘입니다. 이 알고리즘은 O(log n)의 시간 복잡도를 가집니다. 아래에서는 C와 Python에서 이분탐색을 어떻게 구현할 수 있는지 살펴보겠습니다.

C

• C에서 이분탐색을 구현할 때는 주로 배열과 인덱스를 사용합니다.
• 표준 라이브러리에서는 bsearch 함수를 제공하기도 하지만, 대부분의 경우 직접 구현합니다.
• 직접 구현할 경우 낮은 수준의 메모리 제어와 최적화가 가능하며, 포인터를 활용할 수 있습니다.

#include <stdio.h>

int binary_search(int arr[], int size, int target) {
    int left = 0, right = size - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int index = binary_search(arr, 5, 3);
    if (index != -1) printf("Element found at index %d\n", index);
    else printf("Element not found\n");
    return 0;
}

Python

• Python에서는 리스트와 슬라이싱을 이용하여 이분탐색을 쉽게 구현할 수 있습니다.
• bisect 모듈을 사용하면 더 간편하게 이분탐색을 수행할 수 있습니다.
• Python은 높은 수준의 표준 라이브러리와 추상화를 제공하므로 구현이 간단합니다.

from bisect import bisect_left

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

arr = [1, 2, 3, 4, 5]
index = binary_search(arr, 3)
if index != -1:
    print(f"Element found at index {index}")
else:
    print("Element not found")

# Using bisect module
index = bisect_left(arr, 3)
if index != len(arr) and arr[index] == 3:
    print(f"Element found at index {index}")
else:
    print("Element not found")

요약

• C에서는 낮은 수준의 메모리 제어가 가능하며, 성능 최적화를 위한 다양한 방법을 사용할 수 있습니다. 하지만 표준 라이브러리가 제한적입니다.
• Python에서는 높은 수준의 표준 라이브러리와 간결한 문법을 제공하여 이분탐색을 쉽게 구현할 수 있습니다. 하지만, C보다 느린 실행 속도를 가질 수 있습니다.
• 두 언어 모두 이분탐색을 구현할 수 있으나, 구현의 복잡성과 실행 속도, 라이브러리의 지원 등에서 차이가 있습니다.