#pragma warning(disable:4996)
/*
#include<stdio.h>
int main() {
int a, c;
scanf_s("%d", &a);
int b[100005] = { 0 };
int max = 0;
for (int i = 1; i <= a; i++) {
scanf_s("%d", &c);
b[c] += 1;
if (max < c) {
max = c;
}
}
for (int i = 0; i <= max; i++)
{
for (int j = 0; j < b[i]; j++) {
printf("%d ", i);
}
}
return 0;
}*/
/*
//병합정렬
#include<stdio.h>
int sort[100005];
void merge(int a[], int m, int mid, int n)
{
int i, j, k,t;
i = m;
j = mid + 1;
k = m;
//정렬하는 부분
while (i <= mid && j <= n)
{
if (a[i] <= a[j])
{
sort[k] = a[i];
i++;
}
else
{
sort[k] = a[j];
j++;
}
k++;
}
//정렬되고 남은 부분 배열에 입력
if (i > mid)
{
for (t = j; t <= n; t++, k++)
{
sort[k] = a[t];
}
}
else
{
for (t = i; t <= mid; t++, k++)
{
sort[k] = a[t];
}
}
//sort 배열에 있는 값을 a배열에 입력
for (t = m; t <= n; t++) {
a[t] = sort[t];
}
}
void mergeSort(int a[], int m, int n)
{
if (m<n)
{
int mid = (m + n) / 2;
mergeSort(a, m, mid);
mergeSort(a, mid + 1, n);
merge(a,m,mid,n);
}
}
int main()
{
int n;
int a[100005] = { 0 };
scanf_s("%d", &n);
for (int i = 0; i < n; i++)
{
scanf_s("%d", &a[i]);
}
mergeSort(a, 0, n - 1);
for (int i = 0; i < n; i++) {
printf("%d ", a[i]);
}
return 0;
}
*/
/*
#include<stdio.h>
void f(int* pi, int* pj) {
int temp;
temp = *pi;
*pi = *pj;
*pj = temp;
}
int main() {
int i,j;
scanf_s("%d %d", &i,&j);
f(&i,&j);
printf("%d %d", i,j);
return 0;
}*/
/* DFS
#include<stdio.h>
int count=0;
int a[10][10] = { 0 };
void f(int i, int j, int b)
{
if (i<1 || i>7 || j<1 || j>7 || a[i][j] != b)
{
return;
}
count++;
a[i][j] = 0;
f(i + 1, j, b);
f(i, j + 1, b);
f(i - 1, j, b);
f(i, j - 1, b);
}
int main()
{
int c = 0;
for (int i = 1; i <= 7; i++)
{
for (int j = 1; j <= 7; j++)
{
scanf_s("%d", &a[i][j]);
}
}
for (int i = 1; i <= 7; i++)
{
for (int j = 1; j <= 7; j++)
{
count = 0;
if (a[i][j] != 0)
{
f(i, j, a[i][j]);
}
if (count >= 3) {
c++;
}
}
}
printf("%d", c);
return 0;
}*/
/*
#include<stdio.h>
int a[25][25] = { 0 };
int count = 0;
void f(int i, int j, int b)
{
if (i < 1 || i>19 || j < 1 || i>19 || a[i][j] != b)
{
return;
}
if (a[i - 1][j + 1] == b)
{
}
if (a[i][j + 1] == b)
{
}
if (a[i+1][j + 1] == b)
{
}
if (a[i+1][j] == b)
{
}
}
int main()
{
for (int i = 1; i <= 19; i++)
{
for (int j = 1; j <= 19; j++)
{
scanf_s("%d", &a[i][j]);
}
}
for (int i = 1; i <= 19; i++)
{
for (int j = 1; j <= 19; j++)
{
count = 0;
if (a[i][j] != 0) {
f(i, j, a[i][j]);
}
}
}
}
이분탐색 이진탐색
binary search
완전탐색
-순차탐색
-dfs
-bfs
-bs
정렬이 되어있는 데이터에서
1 7 8 9 10 55 60 80 91
찾으려는 데이터가 중간에 있는 값보다 큰지 작은지 비교해서
범위를 반씩 줄여나간다
*/
/*
#include<stdio.h>
#define size 10
int a[size] = { 1,3,5,7,9,11,13,15,17,19 };
int f(int z, int n, int b)
{
int mid = (z + n) / 2;
if (z >= n)
{
if (b != a[z]) return -1;
else return z;
}
if (b == a[mid])
{
return mid;
}
else if (b < a[mid])
{
f(z, mid - 1, b);
}
else
{
f(mid + 1, n, b);
}
}
int main()
{
for (int i = 0; i < size; i++)
{
printf("%d\n", f(0, size - 1, a[i]));
}
return 0;
}
*/
/*이분탐색*/
#include<stdio.h>
int a[100005] = { 0 };
int f(int z, int n, int b)
{
int mid = (z + n) / 2;
if (z >= n)
{
if (b != a[z]) return -1;
else return z;
}
if (b == a[mid])
{
return mid;
}
else if (b < a[mid])
{
f(z, mid - 1, b);
}
else
{
f(mid + 1, n, b);
}
}
int main()
{
int n, m, b;
int r[100005] = { 0 };
scanf_s("%d", &n);
for (int i = 0; i < n; i++)
{
scanf_s("%d", &a[i]);
}
scanf_s("%d", &m);
for (int i = 0; i < m; i++)
{
scanf_s("%d", &r[i]);
//f(a, 0, n, b);
}
for (int i = 0; i < m; i++)
{
printf("%d ", (f(0,n,r[i])==-1? -1: f(0, n, r[i])+1));
//printf("%d ", r[i]);
}
return 0;
}