이진 탐색(Binary Search) 알고리즘 - C언어, Java, Python 예시코드, UpperBound, LowerBound

이진탐색

 

 

이진 탐색(Binary Search)

이진 탐색(Binary Search)은 정렬된 배열에서 원하는 값을 빠르게 찾아내는 효율적인 알고리즘입니다. 이진 탐색은 중간값을 반복적으로 비교하며 탐색 범위를 반으로 줄여 나가므로, 데이터의 크기가 클수록 매우 효과적입니다.

---

 

1. 이진 탐색의 개념

이진 탐색은 다음의 과정을 통해 동작합니다:

1. 배열의 중간값을 확인합니다.
2. 찾고자 하는 값이 중간값보다 작으면 탐색 범위를 왼쪽 절반으로 좁힙니다.
3. 찾고자 하는 값이 중간값보다 크면 탐색 범위를 오른쪽 절반으로 좁힙니다.
4. 원하는 값을 찾을 때 까지 위 과정을 반복합니다.

이진 탐색은 정렬된 배열에서만 동작한다는 점에 유의해야 합니다.

---

 

2. 이진 탐색의 동작 원리

1. 초기 배열: [1, 3, 5, 7, 9, 11], 찾고자 하는 값: 7
2. 중간값 계산: (0 + 5) / 2 = 2 → 중간값: 5
3. 7 > 5 이므로 오른쪽 절반 탐색: [7, 9, 11]
4. 다시 중간값 계산: (3 + 5) / 2 = 4 → 중간값: 9
5. 7 < 9 이므로 왼쪽 절반 탐색: [7]
6. 값 7을 찾음.

---

 

반응형

3. Upper Bound와 Lower Bound

Lower Bound

• Lower Bound는 배열에서 찾고자 하는 값 이상이 처음 나타나는 위치를 반환합니다.
• 예를 들어, 배열 [1, 2, 4, 4, 5]에서 값 4의 Lower Bound는 인덱스 2입니다.

Upper Bound

• Upper Bound는 배열에서 찾고자 하는 값보다 큰 값이 처음 나타나는 위치를 반환합니다.
• 예를 들어, 배열 [1, 2, 4, 4, 5]에서 값 4의 Upper Bound는 인덱스 4입니다.

---

 

4. 이진 탐색 구현 예시 코드

C 언어 구현

#include <stdio.h>

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

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

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

int main() {
    int arr[] = {1, 2, 4, 4, 5};
    int size = sizeof(arr) / sizeof(arr[0]);
    printf("Lower Bound of 4: %d\n", lowerBound(arr, size, 4));
    printf("Upper Bound of 4: %d\n", upperBound(arr, size, 4));
    return 0;
}

 

Java 구현

import java.util.*;

public class BinarySearch {
    public static int binarySearch(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == target)
                return mid;
            else if (arr[mid] < target)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return -1;
    }

    public static int lowerBound(int[] arr, int target) {
        int left = 0, right = arr.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] < target)
                left = mid + 1;
            else
                right = mid;
        }
        return left;
    }

    public static int upperBound(int[] arr, int target) {
        int left = 0, right = arr.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] <= target)
                left = mid + 1;
            else
                right = mid;
        }
        return left;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 4, 4, 5};
        System.out.println("Lower Bound of 4: " + lowerBound(arr, 4));
        System.out.println("Upper Bound of 4: " + upperBound(arr, 4));
    }
}

 

Python 구현

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

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

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

# Example usage
arr = [1, 2, 4, 4, 5]
print("Lower Bound of 4:", lower_bound(arr, 4))
print("Upper Bound of 4:", upper_bound(arr, 4))

---

5. 이진 탐색의 장단점

장점

1. 시간 효율성: O(log N)의 시간 복잡도를 가지며, 큰 데이터 집합에서 매우 빠르게 동작합니다.
2. 구현 용이성: 간단한 논리와 코드로 구현이 가능합니다.

단점

1. 정렬 필요: 배열이 정렬되어 있지 않다면, 먼저 정렬해야 하므로 O(N log N)의 추가 비용이 발생합니다.
2. 유연성 부족: 이진 탐색은 선형 구조에만 적용할 수 있으며, 동적 데이터에서는 사용하기 어렵습니다.

이진 탐색은 컴퓨터 과학에서 매우 중요한 알고리즘으로, 정렬된 데이터에서의 빠른 검색이 필요한 다양한 문제에 활용됩니다.