/*
포인터 복습
구조체
재귀
---------midterm
파일입출력
연결리스트
bitwise
스택, 큐
--------
#include <stdio.h>
#include <stdlib.h> // qsort
int compare(int* pa, int* pb)
{
if(*pa < *pb) return 1;
else if(*pa > *pb) return -1;
else return 0;
}
int main()
{
int a[500]={5,7,3,10,2,1};
for(int i=0;i<6;i++)
printf("%d ",a[i]);
printf("\n");
qsort(a,6,sizeof(int),compare);
// qsort(배열첫번째원소의주소, 데이터갯수, 데이터크기, 정렬기준함수)
for(int i=0;i<6;i++)
printf("%d ",a[i]);
return 0;
}
*/
/*
3002 기억력 테스트3
#include <stdio.h>
int a[1000000]={};
int bs(int s, int e, int k)
{
if(s>e) return -1;
int mid = (s+e)/2;
if(a[mid]==k) return mid+1;
else if(a[mid]>k) return bs(s,mid-1,k);
else return bs(mid+1,e,k);
}
int main()
{
int n,m,i,q;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
int start=0;
int end=n-1;
scanf("%d",&m);
for(i=0;i<m;i++)
{
scanf("%d",&q);
printf("%d ",bs(start,end,q));
}
return 0;
}
*/
/*
2633 Lower Bound
#include <stdio.h>
int a[100000]={};
int bs(int s, int e, int k)
{
if(s>e) return ;
int mid = (s+e)/2;
if(a[mid]>=k)
{
if(a[mid-1]<k) return mid;
else return bs(s,mid-1,k);
}
else return bs(mid+1,e,k);
}
int main()
{
int n,k,i;
scanf("%d %d",&n,&k);
int start=1;
int end=n;
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
if(a[n]<k)
{
printf("%d",n+1);
}
else
{
printf("%d",bs(start,end,k));
}
return 0;
}
*/
이진 탐색 - 왜 순차 탐색 대신 이진 탐색을 써야하고 데이터의 위치를 왜 받아야할까
정렬 안한 배열 따로 만들어야함
#include <stdio.h>
#include <stdlib.h>
int a[50000]={};
int compare(int* pa, int* pb)
{
if(*pa < *pb) return -1;
else if(*pa > *pb) return 1;
else return 0;
}
int bs(int s, int e, int k)
{
}
int main()
{
int n,i;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
int start=0;
int end=n-1;
qsort(a,n,sizeof(int),compare);
bs(start,end,k);
return 0;
}