1420: [탐색] 2진 탐색
메모리제한：
128 MB
시간제한：
1.000 S
체점 스타일：
텍스트 비교
만든사람：
제출：
0
통과：
0
문제 설명
정보과학 교과서 169p
----
2진 탐색(binary search)은 원하는 데이터를 찾기 위해서,
정렬되어있는 데이터들의 가운데 값을 반복적으로 찾아 비교하는 탐색 방법이다.
탐색이 한 번씩 진행될 때마다, 찾아보아야하는 데이터의 범위(개수)가 절반 씩 줄어들기 때문에 매우 빠른 탐색이 가능하다.
정렬되어있는 n개의 정수 데이터를 입력받아,
원하는 데이터가 저장된 위치를 찾는 2진탐색 프로그램을 작성해보자.
단, find() 등을 사용할 수 없다.
#include <stdio.h>
int n, d[100010], k, q, x;
int binary_search(int l, int r, int x)
{
if(l>r) return -1; //데이터 x를 못 찾은 경우 -1리턴
int m = (l+r)/2; //가운데 위치 m을 계산하고
if(d[m] == x) //가운데 위치에 찾는 데이터가 있으면, 해당 위치 리턴
return m;
else if(d[m] > x) //찾는 데이터보다 값이 크다면, 왼쪽 부분에 대해서 다시 탐색
return binary_search(l, m-1, x);
else //찾는 데이터보다 값이 작다면, 오른쪽 부분에 대해서 다시 탐색
return binary_search(m+1, r, x);
}
int main()
{
scanf("%d", &n); //데이터 개수 입력
for(int i=1; i<=n; i++) //데이터 입력
scanf("%d", &d[i]);
scanf("%d", &q); //쿼리 개수 입력
for(int i=1; i<=q; i++)
{
scanf("%d", &k);
printf("%d\n", binary_search(1, n, k)); //2진 탐색
}
}
----
2진 탐색(binary search)은 원하는 데이터를 찾기 위해서,
정렬되어있는 데이터들의 가운데 값을 반복적으로 찾아 비교하는 탐색 방법이다.
탐색이 한 번씩 진행될 때마다, 찾아보아야하는 데이터의 범위(개수)가 절반 씩 줄어들기 때문에 매우 빠른 탐색이 가능하다.
정렬되어있는 n개의 정수 데이터를 입력받아,
원하는 데이터가 저장된 위치를 찾는 2진탐색 프로그램을 작성해보자.
단, find() 등을 사용할 수 없다.
#include <stdio.h>
int n, d[100010], k, q, x;
int binary_search(int l, int r, int x)
{
if(l>r) return -1; //데이터 x를 못 찾은 경우 -1리턴
int m = (l+r)/2; //가운데 위치 m을 계산하고
if(d[m] == x) //가운데 위치에 찾는 데이터가 있으면, 해당 위치 리턴
return m;
else if(d[m] > x) //찾는 데이터보다 값이 크다면, 왼쪽 부분에 대해서 다시 탐색
return binary_search(l, m-1, x);
else //찾는 데이터보다 값이 작다면, 오른쪽 부분에 대해서 다시 탐색
return binary_search(m+1, r, x);
}
int main()
{
scanf("%d", &n); //데이터 개수 입력
for(int i=1; i<=n; i++) //데이터 입력
scanf("%d", &d[i]);
scanf("%d", &q); //쿼리 개수 입력
for(int i=1; i<=q; i++)
{
scanf("%d", &k);
printf("%d\n", binary_search(1, n, k)); //2진 탐색
}
}
입력 설명
첫 번째 줄에 데이터의 개수(n)가 입력된다.
두 번째 줄에는 서로 다른 n개의 정수 데이터(k)가 오름차순으로 스페이스를 사이에 두고 한 줄로 입력된다.
세 번째 줄에는 쿼리 개수(q)가 입력된다.
네 번째 줄부터 q개의 줄에 거쳐, 위치를 찾아야하는 데이터(x)가 한 줄에 1개씩 입력된다.
[1 <= n <= 100000]
[0 <= k <= 1000000]
[1 <= q <= 100000]
[0 <= x <= 1000000]
두 번째 줄에는 서로 다른 n개의 정수 데이터(k)가 오름차순으로 스페이스를 사이에 두고 한 줄로 입력된다.
세 번째 줄에는 쿼리 개수(q)가 입력된다.
네 번째 줄부터 q개의 줄에 거쳐, 위치를 찾아야하는 데이터(x)가 한 줄에 1개씩 입력된다.
[1 <= n <= 100000]
[0 <= k <= 1000000]
[1 <= q <= 100000]
[0 <= x <= 1000000]
출력 설명
q개의 데이터 x가 저장되어있는 위치를 한 줄에 1개씩 출력한다.
데이터 x를 찾을 수 없는 경우에는 -1을 출력한다.
데이터 x를 찾을 수 없는 경우에는 -1을 출력한다.
입력 예시 복사
5
3 4 7 8 9
3
8
7
2
출력 예시 복사
4
3
-1