[알고리즘]#1_이분 탐색(Binary Search)

 

#0. 개념

 

1. 이분 탐색?

[정의] : 이분 탐색은 정렬된 배열에서 특정 값을 찾기위해 사용되는 탐색 알고리즘입니다.

[동작 방식]

1. 먼저, 배열의 왼쪽 경계와 오른쪽 경계를 설정합니다.
2. 중간 값을 얻어 찾고자하는 특정 값과 그 크기를 비교합니다.
3. 위 비교 연산의 결과에 따라서 왼쪽 경계 혹은 오른쪽 경계를 변경합니다.
4. 위 작업을 반복하며, 최종적으로 특정 값을 찾아냅니다.

* 주의할 점 : 이분 탐색은 '정렬된' 배열에 사용되는 탐색 알고리즘입니다.

 

2. 코드

int BinarySearch(vector<int> v, int l, int r, int x) {
    while (l <= r) {
        int mid = l + (r - l) / 2;

        // 찾고자 하는 값이 중간값과 같은 경우
        if (v[mid] == x) return mid;

        // 찾고자 하는 값이 중간값보다 작은 경우, 왼쪽 배열 탐색
        if (v[mid] > x) r = mid - 1;

        // 찾고자 하는 값이 중간값보다 큰 경우, 오른쪽 배열 탐색
        else l = mid + 1;
    }

    // 찾고자 하는 값이 배열 내부에 존재하지 않는 경우
    return -1;
}

 

Details

1. left와 right를 통해 mid 값을 계산합니다.
2. mid 값과 x값을 비교합니다.
3. mid 값과 x값이 같을 경우, 바로 mid 값을 반환합니다.
4. mid 값이 x값 보다 작을 경우, right 값을 mid-1 위치로 변경합니다.
5. mid 값이 x값 보다 클 경우, left값을 mid+1 위치로 변경합니다.
6. 위 작업을 반복하며, 최종적으로 x값과 같은 값을 갖는 mid 값을 찾아냅니다.

 

---

 

#1. 예제

 

1. 예제-1

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int N, M;
    vector<int> nVector; vector<int> mVector;

    cin >> N;
    for(int i=0; i<N; i++)
    {
        int tmp;
        cin >> tmp;

        nVector.push_back(tmp);
    }

    cin >> M;
    for(int i=0; i<M; i++)
    {
        int tmp2;
        cin >> tmp2;

        mVector.push_back(tmp2);
    }

    sort(begin(nVector), end(nVector));

    for(int i=0; i<M; i++)
    {
        int right = N-1;
        int left = 0;
        bool check = false;
        while(left <= right)
        {
            int mid = (left + right)/2;
            if (mVector[i] == nVector[mid])
                check = true;
            if (mVector[i] < nVector[mid])
                right = mid-1;
            else
                left = mid+1;
        }

        if(check == true)
            cout << 1 << " ";
        else
            cout << 0 << " ";
    }
}

 

Details

BOJ 문제 중 10815번(숫자 카드) 문제입니다. 가장 먼저, 이진 탐색을 활용하기 위해 배열을 정렬합니다. 그리고, 위에서 살펴본 이진 탐색의 기본 알고리즘을 구현한 코드를 적용해 쉽게 풀 수 있는 문제입니다.

 

2. 예제-2

#include<iostream>
#include<algorithm>
using namespace std;

int N, M;
int arr[100001];

void BinarySearch(int num)
{
    int left = 0;
    int right = N-1;
    
    while(left <= right)
    {
        int mid = (left + right)/2;
        if (arr[mid] == num)
        {
            cout << 1 << endl;
            return;
        }
        else if(arr[mid] > num) right = mid-1;
        else left = mid+1;
    }
    cout << 0 << endl;
    return;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin >> N;
    
    for(int i=0; i<N; i++)
    {
        cin >> arr[i];
    }
    
    sort(arr, arr+N);
    
    cin >> M;
    
    for(int i=0; i<M; i++)
    {
        int x;
        cin >> x;
        BinarySearch(x);
    }
    
}

 

Details

BOJ 알고리즘 1920번(수 찾기) 문제입니다.먼저, 이진 탐색을 활용하기 위해 배열을 정렬하고 있습니다.마지막으로 위에서 살펴본 이진 탐색 알고리즘 코드를 적용하여 쉽게 문제를 풀 수 있습니다!

 

---