/*
#include<stdio.h>
int main()
{
int n,s,i,j;
int arr[100001]={};
//arr[i] : i라는 숫자가 입력된 횟수
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&s);
arr[s]++;
}
for(i=0;i<=100000;i++)
{
if(arr[i]!=0)
{
// i를 arr[i]번 출력
// 6을 (arr[6]=2)번 출력
for(j=1;j<=arr[i];j++)
{
printf("%d ",i);
}
}
}
}
1. 퀵정렬 직접 구현 (x)
2. 퀵정렬 함수 사용법 익히기
&arr[0] -> arr
*/
/*
#include <stdio.h>
#include <stdlib.h> // 퀵정렬 함수 여기 들어있음!
int compare(int* pa, int* pb)
{
// pa : 왼쪽값의 주소 // *pa : 왼쪽값
// pb : 오른쪽값의 주소 // *pb :오른쪽값
if(*pa > *pb ) return 1;
else return 0;
}
int main()
{
int arr[50]={};
int i, n;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&arr[i]);
//정렬기준
qsort(arr,n,sizeof(int),compare);
// qsort(정렬할배열의 첫원소의 주소, 정렬할 데이터 갯수, 정렬할 데이터 크기, 정렬기준함수)
for(i=0;i<n;i++)
printf("%d ",arr[i]);
return 0;
}
#include<stdio.h>
#include<stdlib.h>
int compare(int*pa, int *pb)
{
if(*pa > *pb) return 1;
else return 0;
}
int main()
{
int arr[101]={};
int i;
for(i=0;i<5;i++)
{
scanf("%d",&arr[i]);
}
qsort(arr,5,sizeof(int),compare);
printf("%d",arr[2]);
return 0;
}
*/
/*
#include<stdio.h>
#include<stdlib.h>
int compare(int *pa,int *pb)
{
if(*pa > *pb) return 1;
else return 0;
}
int main()
{
int arr[1001]={};
int i,m,n;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&arr[i]);
}
qsort(&arr[1],n,sizeof(int),compare);
m=arr[n]-arr[1];
printf("%d",m);
}
이분탐색 ( 이진탐색) binary search
up-down 게임
-> 정렬된 데이터일때만!!!!
*/
#include <stdio.h>
int arr[1000001]={};
int bs(int s, int e, int k) // arr[s] ~arr[e]에서 k값의 위치 리턴
{
int mid=(s+e)/2;
if(arr[mid]==s||arr[mid]==e)
{
return -1;
}
else
{
if(arr[mid]==k)
{
return mid;
}
else if(arr[mid]>k)
{
return bs(s,mid-1,k);
}
else
{
return bs(mid+1,e,k);
}
}
}
int main()
{
int i,j,m,n,a;
int index;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&arr[i]);
}
scanf("%d",&m);
for(j=1;j<=m;j++)
{
scanf("%d",&a);
index = bs(1,n,a);
printf("%d ",index);
}
// arr[1] ~ arr[100]에서 46의 위치 리턴
}