자료구조 - 이진 탐색

[이진 탐색]

이진 탐색(Binary Search)은 정렬된 배열에서 매우 효율적으로 원하는 값을 찾을 수 있는 탐색 알고리즘입니다.

배열을 반으로 나누어 탐색 범위를 좁혀가며 원하는 값을 찾기 때문에, 큰 데이터셋에서도 빠르게 작동합니다.

 

 

이진 탐색의 작동원리

1. 배열의 중간 요소를 선택하여 찾고자 하는 값과 비교합니다.
2. 찾고자 하는 값이 중간 요소보다 작으면, 배열의 왼쪽 반을 탐색합니다.
3. 찾고자 하는 값이 중간 요소보다 크면, 배열의 오른쪽 반을 탐색합니다.
4. 위 과정을 찾고자 하는 값을 발견하거나 탐색 범위가 없을 때까지 반복합니다.

 

이진 탐색은 순환 방식과 반복 방식 모두 사용이 가능합니다.

순환 방식에 대해서 먼저 알아보겠습니다.

 

 

이진 탐색(순환) 의사 코드

함수 binarySearch(arr, low, high, key):
    if low > high:
        반환 -1 // key를 찾을 수 없는 경우
    mid = (low + high) / 2
    if arr[mid] == key:
        반환 mid // key의 인덱스 반환
    else if arr[mid] > key:
        반환 binarySearch(arr, low, mid - 1, key)
    else:
        반환 binarySearch(arr, mid + 1, high, key)

 

 

이진 탐색(순환) 코드

#include <iostream>
#include <vector>

using namespace std;

// 순환 방식의 이진 탐색 함수
int binarySearchRecursive(const vector<int>& arr, int low, int high, int key) 
{
    if (low > high) 
    {
        return -1; // key를 찾을 수 없는 경우
    }
    int mid = low + (high - low) / 2;
    if (arr[mid] == key) 
    {
        return mid; // key의 인덱스 반환
    } 
    else if (arr[mid] > key)
    {
        return binarySearchRecursive(arr, low, mid - 1, key);
    } 
    else 
    {
        return binarySearchRecursive(arr, mid + 1, high, key);
    }
}

int main() 
{
    vector<int> arr = {11, 22, 25, 45, 64}; // 정렬된 예제 배열
    int key = 22; // 찾고자 하는 값

    // 순환 방식의 이진 탐색 수행
    int result = binarySearchRecursive(arr, 0, arr.size() - 1, key);

    // 결과 출력
    if (result != -1) 
    {
        cout << "값 " << key << "을(를) 인덱스 " << result << "에서 찾았습니다." << endl;
    } 
    else 
    {
        cout << "값 " << key << "을(를) 배열에서 찾을 수 없습니다." << endl;
    }

    return 0;
}

 

 

 

이진 탐색(반복) 의사 코드

함수 binarySearch(arr, key):
    low = 0
    high = arr의 길이 - 1
    while low <= high:
        mid = (low + high) / 2
        if arr[mid] == key:
            반환 mid // key의 인덱스 반환
        else if arr[mid] > key:
            high = mid - 1
        else:
            low = mid + 1
    반환 -1 // key를 찾을 수 없는 경우

 

 

이진 탐색(반복) 코드

#include <iostream>
#include <vector>

using namespace std;

// 반복 방식의 이진 탐색 함수
int binarySearchIterative(const vector<int>& arr, int key)
{
    int low = 0;
    int high = arr.size() - 1;
    while (low <= high)
    {
        int mid = low + (high - low) / 2;
        if (arr[mid] == key) 
        {
            return mid; // key의 인덱스 반환
        } 
        else if (arr[mid] > key)
        {
            high = mid - 1;
        }
        else 
        {
            low = mid + 1;
        }
    }
    return -1; // key를 찾을 수 없는 경우
}

int main() 
{
    vector<int> arr = {11, 22, 25, 45, 64}; // 정렬된 예제 배열
    int key = 22; // 찾고자 하는 값

    // 반복 방식의 이진 탐색 수행
    int result = binarySearchIterative(arr, key);

    // 결과 출력
    if (result != -1)
    {
        cout << "값 " << key << "을(를) 인덱스 " << result << "에서 찾았습니다." << endl;
    } 
    else
    {
        cout << "값 " << key << "을(를) 배열에서 찾을 수 없습니다." << endl;
    }

    return 0;
}

 

 

이진 탐색 예제

정렬된 배열: [11, 22, 25, 45, 64]
찾고자 하는 값: 22

이진 탐색의 과정 설명 (반복 방식)
1. 초기 상태:
    low = 0, high = 4 (배열의 첫 번째와 마지막 인덱스)
    arr = [11, 22, 25, 45, 64]

2. 첫 번째 반복:
    mid = (low + high) / 2 = (0 + 4) / 2 = 2
    arr[mid] = arr[2] = 25
    25는 22보다 크므로, 오른쪽 반을 버리고 왼쪽 반을 탐색
    high = mid - 1 = 2 - 1 = 1

3. 두 번째 반복:
    low = 0, high = 1
    mid = (low + high) / 2 = (0 + 1) / 2 = 0
    arr[mid] = arr[0] = 11
    11은 22보다 작으므로, 왼쪽 반을 버리고 오른쪽 반을 탐색
    low = mid + 1 = 0 + 1 = 1

4. 세 번째 반복:
    low = 1, high = 1
    mid = (low + high) / 2 = (1 + 1) / 2 = 1
    arr[mid] = arr[1] = 22
    22는 22와 같으므로, 값을 찾음
    반환 mid = 1

 

 

이진 탐색 장단점

 

장점 :

1. 효율성: 시간 복잡도가 O(log⁡n)O(\log n)O(logn)로 매우 효율적입니다.
2. 간단한 구현: 상대적으로 이해하고 구현하기 쉽습니다.

단점 :

1. 정렬 필요: 데이터가 미리 정렬되어 있어야 합니다.
2. 복잡도: 순환 방식의 경우 스택 오버플로우 문제가 발생할 수 있습니다.

 

 

시간 복잡도

 

• 최선의 경우: O(1)O(1)O(1) (찾고자 하는 값이 배열의 중간 요소일 때)
• 최악의 경우: O(log⁡n)O(\log n)O(logn) (찾고자 하는 값이 배열의 양 끝에 있거나 배열에 없을 때)
• 평균의 경우: O(log⁡n)O(\log n)O(logn)