[Jungol] 정올 3517 Tutorial : 이진탐색(Binary Search-이진검색)

출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2857&sca=30

Approach

- 배열의 원소가 정렬되어서 주어지므로 별도로 정렬할 필요가 없습니다.

Binary Search (이분 탐색) 

Binary Search (이분 탐색)

---

#include <stdio.h>
#define LM 500005
int N, Q, arr[LM];
void input() {
    scanf("%d", &N);
    for (int i = 0; i < N; ++i) {
        scanf("%d", arr + i);
    }
}
 
int bSearch(int s, int e, int target) {
    while (s <= e) {
        int m = (s + e) / 2;
        if (arr[m] == target) return m;
        if (arr[m] < target) s = m + 1;
        else e = m - 1;
    }
    return -1;
}
 
void process() {
    int i, target;
    scanf("%d", &Q);
    for (i = 0; i < Q; ++i) {
        scanf("%d", &target);
        int res = bSearch(0, N - 1, target);
        printf("%d ", res);
    }
}
 
int main() {
    input();
    process();
    return 0;
}