/*
#include <stdio.h>
typedef struct
{
int score,num;
}student;
int main()
{
int n,a,j,i;
student arr[50001]={};
student t;
scanf("%d",&n);
for(i=1; i<=n ;i++)
{
scanf("%d",&arr[i].score);
}
for(i=1; i<n; i++)
{
for(j=1; j<=n-i; j++)
{
if(arr[j].score>arr[j+1].score)
{
t=arr[j];
arr[j]=arr[j+1];
arr[j+1]=t;
arr[j].num=j;
}
}
}
for(int j = 1; j<=n; j++)
{
printf("%d ",arr[j].num);
}
return 0;
}
*/
/*
#include <stdio.h>
int arr[50001]={}; // 정렬 한 배열
int bs(int s, int e, int k)
// arr[start] ~ arr[end] 에 k 값의 위치를 리턴, 없다면 -1리턴
{
if(s>e) return -1;
int mid = (s+e)/2;
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 n,a,j,i,t;
int brr[50001]={}; // 정렬 안 한 배열
scanf("%d",&n);
for(i=1; i<=n ;i++){
scanf("%d",&arr[i]);
brr[i]=arr[i];
}
for(i=1; i<n; i++){
for(j=1; j<=n-i; j++){
if(arr[j]>arr[j+1]){
t=arr[j];
arr[j]=arr[j+1];
arr[j+1]=t;
}
}
}
for(i=1; i<=n; i++){
// brr[i]가 arr에 어디에 있는지?
printf("%d ",bs(1,n,brr[i])-1);
}
return 0;
}
이분 탐색
binary search -> bs
<< 정렬이 되어있는 경우, 반씩 나누면서 찾기>>
5번만 물어보면 k가 어디있는지? 없는지? 알 수 있따!
순차 탐색
100번 물어보면 무조건 k가 어디이쓴지?없는지?
2084
#include <stdio.h>
int arr[10000000]={};
int bs(int s,int e,int k)
{
if(s>e) return -1; // 못찾았으면?
int mid = (s+e)/2;
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 n,m,s,a;
scanf("%d",&n);
for(int i=1; i<=n; i++)
{
scanf("%d",&arr[i]);
}
scanf("%d",&s);
for(int i=1; i<=s; i++)
{
scanf("%d",&a);
printf("%d\n",bs(1,n,a));
}
return 0;
}
*/
#include <stdio.h>
int bs(int s,int e,int k)
{
if(s>e) return -1;
int mid = (s+e)/2;
if(arr[mid]==k) bs
}
int main()
{
}