문제 N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다. 출력 M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다. 예제 입력 1 5 4 1 5 2 3 5 1 3 7 9 5 예제 출력 1 1 1 0 0 1 풀이 이진 탐색과 퀵정렬을 이용해서 풀었다. 둘의 ..

순서대로 나열되어 있는 배열이 있습니다. 이 배열에서 target 값을 찾으려 하는데, 배열 요소가 100만개라 모두 비교하면 시간이 많이 걸립니다. 이때 더 빠르게 target 값을 찾을 순 없을까요? 이 필요성을 채워주는 것이 이분 탐색 알고리즘입니다. 📌 이분 탐색 정의 이분 탐색은 정렬된 배열을 1/2씩 줄여서 타겟 값을 찾아나가는 알고리즘입니다. 이분 탐색의 프로세스는 다음과 같습니다. (1) 배열의 중간 값을 찾는다. (2) target 값과 중간 값을 비교하여 (low, same, high)큰지, 작은지, 같은지를 판단한다. (3) target이 작다면 중간 값 이전의 배열을, 크다면 중간 값 이후의 배열을 대상으로 다시 이분 탐색을 진행한다. (4) 만약 같다면, 중간 값이 바로 targe..