/*
#include <stdio.h>
#include <stdlib.h>
int main()
{
printf("초신성과 초거성\n");
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int s, i, j;
int a[100001]={};
scanf("%d", &s);
for(i=1; i<=s; i++)
{
scanf("%d", &j);
a[j]++;
}
for(i=0; i<=100000; i++)
{
while(a[i]>0)
{
printf("%d ", i);
a[i]--;
}
}
return 0;
}
*/
/*
#include <stdio.h>
typedef struct
{
char name[51];
int score;
}stu;
int main()
{
stu a[101]={};
int s, i, j, r[55];
scanf("%d", &s);
for(i=1; i<=s; i++)
{
scanf("%s %d", a[i].name, &a[i].score);
r[i]=1;
}
for(i=1; i<=s; i++)
{
for(j=1; j<=s; j++)
{
if(a[i].score < a[j].score)
{
r[i]++;
}
}
}
for(i=1; i<=s; i++)
{
if(r[i]==3)
{
printf("%s", a[i].name);
}
}
return 0;
}
*/
/*
#include <stdio.h>
typedef struct
{
char name[51];
int score;
}stu;
int main()
{
stu a[101]={};
stu r;
int s, i, j;
scanf("%d", &s);
for(i=1; i<=s; i++)
{
scanf("%s %d", a[i].name, &a[i].score);
}
for(i=1; i<s; i++)
{
for(j=1; j<=s-i; j++)
{
if(a[j].score < a[j+1].score)
{
r = a[j];
a[j] = a[j+1];
a[j+1] = r;
}
}
}
printf("%s ", a[3].name);
return 0;
}
1 2 3 4 5
2 23 55 87 100
5 2 100 55
-1 1 5 3
100만개의 숫자를 불러주고,
10만개의 숫자 위치를 찾아봐
1개의 위치를 찾으려면 100만번 비교
10만개의 위치를 찾으려면 10만*100만 번 비교
정렬이 되어있는 데이터가 들어온다면???
전부 다 찾아보지 않아도 돼
up-down game
1~ 50사이의 임의의 수 찾기
정렬되어있는 100만개의 숫자를 갖고있어.
숫자 하나를 찾고싶으면 , 1번 ~100만번까지 순서대로 보는것 보다는,
1. 50만번째 숫자가 그 숫자와 같나요? 큰가요? 작은가요?
2. 찾아야 할 데이터의 갯수가 반으로 줄어든다 ( 탐색 범위를 줄여간다)
3. 이런식으로 반복하다보면 훨씬 빠르게 찾을 수 있따
이분탐색 = 이진탐색 = binary search
이등분 : 반으로 똑같이 쪼개는거
이분 : 반으로 쪼개는거
결론!!
정렬된 배열이 주어졌을때, 데이터를 찾고싶다면 (이진탐색)을 쓰면 빠르다.
이진탐색을 만들어보자.
힌트! 재귀함수를 쓰면 간단해진다. but 재귀함수를 쓰지 않아도 가능함.
숙제
3002번 이진탐색으로 풀어보기.
*/