[이분탐색] BOJ 1920번 수 찾기

https://www.acmicpc.net/problem/1920

1920번: 수 찾기

- 문제 파악

N 개의 배열을 주어지고 이 안에서 주어지는 M개의 정수가 있는지 판별하라. 주어지는 정수가 존재한다면 1, 아니면 0을 주어지는 정수에 따라 각각 출력하라.

 

- 정답

이분탐색 입문 문제

시작 인덱스와 종료 인덱스 그리고 중간 인덱스를 각각 초기화 시킨 다음

중간 인덱스의 값과 확인하고 싶은 값의 크기에 따라 시작 인덱스 또는 종료 인덱스 값을 바꿔가면서

확인하고 싶은 값을 빠르게 찾는 알고리즘이다.

 

아래 코드 중에서 

중간 인덱스와 시작 인덱스 또는 종료 인덱스가 같은지 비교하는 부분이 있는데, 이 부분을 시작 인덱스 또는 종료 인덱스를 다시 정의 하는 부분 뒤에 놔둬서 제대로 된 값이 나오지 못했다.

 

#include "bits/stdc++.h"

using namespace std;

long long arr[100001];
int n, m;

int func(long long k)
{
    int idx_st = 0, idx_ed = n - 1;
    int idx_mid = (idx_st + idx_ed) / 2;

    while (1)
    {

        if (idx_st == idx_mid || idx_ed == idx_mid)
        {
            if (arr[idx_st] == k || arr[idx_ed] == k) return 1;
            else return 0;
        }

        if (arr[idx_mid] > k) idx_ed = idx_mid - 1;
        else if (arr[idx_mid] < k) idx_st = idx_mid + 1;
        else if (arr[idx_mid] == k) return 1;

        if (idx_st == idx_ed)
        {
            if (k == arr[idx_st]) return 1;
            else return 0;
        }
        else if (idx_st > idx_ed) return 0;

        if (arr[idx_st] == k || arr[idx_ed] == k) return 1;

        idx_mid = (idx_st + idx_ed) / 2;

    }
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);

    cin >> n;

    for (int i = 0; i < n; i++)
        cin >> arr[i];

    sort(arr, arr + n);

    cin >> m;

    while (m--)
    {
        long long tmp;
        cin >> tmp;
        cout << func(tmp) << "\n";
    }

}

 

아래는 STL binary_search 함수를 사용한 코드이다.

이분탐색 구현하는 연습은 좋지만 실전에서 위 함수가 사용 가능하다면 사용하는 것이 좋다.

 

#include "bits/stdc++.h"

using namespace std;

long long arr[100001];
int n, m;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);

    cin >> n;

    for (int i = 0; i < n; i++)
        cin >> arr[i];

    sort(arr, arr + n);

    cin >> m;

    while (m--)
    {
        long long tmp;
        cin >> tmp;
        cout << (int)binary_search(arr,arr+n,tmp) << "\n";
    }

}