[백준] 1920번 : 수 찾기

문제

 

---

풀이

 

이분 탐색은 문제의 크기를 반으로 잘라가며 답을 찾는 알고리즘이다.

이런 문제일 때는 주어진 배열을 정렬하고, 배열의 가운데 값(mid)과 목표로 하는 값(target)을 비교한다.

만약 mid==target이면 답을 찾은 것이니 바로 리턴하고

mid<target이면 mid를 기준으로 배열을 잘라 그 오른쪽만 탐색하고

mid>target이면 mid를 기준으로 배열을 잘라 그 왼쪽만 탐색하면 된다.

---

소스코드

 

#include <iostream>
#include <algorithm>

using namespace std;

int A[1000000];

bool binarySearch(int target, int left, int right) {
    while (left <= right) {
        int mid = (left + right) / 2;
        if (target == A[mid])
            return true;
        else if (target < A[mid]) //왼쪽 탐색
            right = mid - 1;
        else if (target > A[mid]) //오른쪽 탐색
            left = mid + 1;
    }
    return false;
}

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

    int N, M, target;

    cin >> N;
    for (int i = 0; i < N; i++)
        cin >> A[i];
    sort(A, A + N); //정렬

    cin >> M;
    for (int i = 0; i < M; i++) {
        cin >> target;
        cout << binarySearch(target, 0, N - 1) << '\n';
    }

}

 

전체 소스코드다.

 

bool binarySearch(int target, int left, int right) {
    while (left <= right) {
        int mid = (left + right) / 2;
        if (target == A[mid])
            return true;
        else if (target < A[mid]) //왼쪽 탐색
            right = mid - 1;
        else if (target > A[mid]) //오른쪽 탐색
            left = mid + 1;
    }
    return false;
}

풀이 그대로 작성했다.

 

www.cplusplus.com/reference/algorithm/binary_search/

binary_search - C++ Reference

근데 세상에 놀랍게도 C++은 binary_search 함수를 제공하고 있었다...