[BaekJoon][1920] 수 찾기

BAEKJOON ONLINE JUDGE

1920 수 찾기

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

이진 탐색

아.. 왜 나는 이진탐색 구현을 매번 실수하지..

quicksort 구현하면 0부터 마지막 배열까지 <---> stl::sort : 0부터 마지막 + 1까지 (개수)

binary search도 마찬가지로  left : 0, right : n - 1 까지 해야하는데 자꾸 n까지로 해서 값이 하나 잘못 들어가는 실수...

#include <stdio.h>
 
int a[100010];
int n, m;
 
void quicksort(int start, int end)
{
    int left = start, right = end;
    int middle = a[(start + end) / 2];
    int temp;
 
    while (left <= right) {
        while (a[left] < middle)     left++;
        while (a[right] > middle)     right--;
 
        if (left <= right) {
            temp = a[left];
            a[left] = a[right];
            a[right] = temp;
            
            left++;
            right--;
        }
    }
 
    if (left < end)        quicksort(left, end);
    if (right > start)    quicksort(start, right);
}
 
int bsearch(int goal)
{
    int left = 0, right = n - 1;
    int middle;
 
    while (left <= right) {
        middle = (left + right) / 2;
 
        if (a[middle] == goal)    return 1;
        else if (goal < a[middle]) 
            right = middle - 1;
        else left = middle + 1;
    }
 
    return 0;
}
 
int main()
{
    int i, num;
 
    scanf("%d", &n);
 
    for (i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
 
    quicksort(0, n - 1);
 
    scanf("%d", &m);
 
    for (i = 0; i < m; i++) {
        scanf("%d", &num);
 
        printf("%d\n", bsearch(num));
    }
 
    return 0;
}