티스토리 뷰

728x90

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

 

1920번: 수 찾기

첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안��

www.acmicpc.net

이분탐색 C++

예 이분탐색 문제입니다

 

정렬 후 이분탐색 끝

놀랍게도 이 쉬운걸 몇번을 틀렸는데요 메모리초과+시간초과가 나왔지만

메모리초과는 로직문제였고 시간초과는..시간단축하는 부가코드 쓰니까 해결

그럼 전 밥을 먹으러 가겠습니다.

요즘은 머리를 쓰기 싫네요. 쉬어가도록하죠

 

소스코드

#include <iostream>
#include <algorithm>
using namespace std;
int num[1000000];

void binarySearch(int key, int n){
    int start = 0;
    int end = n-1;
    int mid;

    while(start <= end){
        mid = (start+end)/2;
        if(num[mid] == key){
            cout << "1\n";
            return;
        }
        else if(num[mid] < key)
            start = mid+1;
        else
            end = mid-1;
    }
    cout << "0\n";
}
int main(){
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for(int i = 0 ; i < n ; i++){
        cin >> num[i];
    }
    sort(num, num+n);
    int k;
    cin >> k;
    int key;
    for(int i = 0; i < k ; i++){
        cin >> key;
        binarySearch(key, n);
    }
    
    return 0;
}
728x90
250x250
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/02   »
1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29
글 보관함