[백준,C++] 1920번: 수 찾기

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

1920번: 수 찾기

#include <iostream>
#include <algorithm>  // for sorting
using namespace std;
const int MAX_SIZE = 100000;

int binarySearch(int arr[], int low, int high, int target) {
    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (arr[mid] == target)
            return 1;  // Element found
        else if (arr[mid] < target)
            low = mid + 1;
        else
            high = mid - 1;
    }

    return 0;  // Element not found
}

int main() {
    // Input the size of the first array
    int n;
    cin >> n;

    // Dynamic allocation of memory for the first array
    int* numbers = new int[n];

    // Input elements for the first array
    for (int i = 0; i < n; i++) {
        cin >> numbers[i];
    }

    // Sort the array (required for binary search)
    sort(numbers, numbers + n);

    // Input the size of the second array
    int m;
    cin >> m;

    // Input elements for the second array
    int* finding = new int[m];

    // Check if each element in the second array is present in the first array using binary search
    for (int i = 0; i < m; i++) {
        cin >> finding[i];
        cout << binarySearch(numbers, 0, n - 1, finding[i]) << endl;
    }

    // Deallocate dynamically allocated memory
    delete[] numbers;
    delete[] finding;

    return 0;
}

 

메인 함수의 작동은 간단하다

정수 M을 받으면
M크기의 배열을 할당하고

정수 N을 받으면 

N크기의 배열을 할당한다

 

그 후 N크기의 배열에 있는 정수들이 M크기 배열에 있는지 확인하려면
binarySearch() 함수를 통해 이진탐색 을 통해 확인한다

 

이진탐색은

low, high를 입력받아

mid를 (low+high)/2로 정의한다

그래서 mid가 우리가 찾는 정수인지 확인한다

아니면 이진 탐색 전 정렬을 했기에 더 초반에 있으면 high를 mid-1로 설정하고

더 후에 있으면 low를 mid+1로 설정해 반복한다

 

그냥 처음부터 찾는거보다 

정렬 O(nlogn)후 이진탐색 O(logn)을 하는 것이 더 좋음을 알게 되었다