정렬된 n개의 데이터 중에서 ‘찾고자 하는 값’이 어디에 위치하는지 확인하는 프로그램을 작성하시오. ‘찾고자 하는 값’이 맨 처음에 존재하면 1을, 그 다음 위치에 존재하면 2를... 출력한다. 만약 존재하지 않는 경우는 0을 출력한다. 실행 파일의 이름은 문제 코드와 동일하며 실행 시간은 0.5초를 초과할 수 없다.

입력 형식

입력 파일의 이름은 INPUT.TXT이다. 첫째 줄에 정수 n이 주어진다. 둘째 줄에는 공백을 사이에 두고 n개의 서로 다른 데이터들이 주어진다. 둘째 줄에는 찾고자 하는 값이 주어진다. n은 100,000,000 이하의 정수고, 각 데이터도 500,000,000 이하의 정수다.

출력 형식

출력 파일의 이름은 OUTPUT.TXT이다. 첫째 줄에 찾고자 하는 값의 위치를 출력한다. 단, 가장 앞쪽에 있는 값의 위치는 1이다. 찾고자 하는 값이 존재하지 않을 경우에는 0을 출력한다.

입력과 출력의 예 1

입력 (INPUT.TXT)

출력 (OUTPUT.TXT)

입력과 출력의 예 2

입력 (INPUT.TXT)

출력 (OUTPUT.TXT)

// 순차 정렬

#include

int a[100000000];

int main()

{

freopen("input.txt","r",stdin);

freopen("output.txt","w",stdout);

int n,i,key;

scanf("%d",&n);

for(i=0;i;i++){ span="" <=""></n;i++){>

scanf("%d",&a[i]);

}

scanf("%d",&key);

for(i=0;i;i++){ span="" <=""></n;i++){>

if(a[i]==key) break;

}

if(i==n) printf("0");

else printf("%d",i+1);

return 0;

}

​

========================

//이분정렬

#include

int a[100000000];

int main()

{

int i, n, key;

int low, high, mid, flag=0;

freopen("input.txt","r",stdin);

freopen("output.txt","w",stdout);

scanf("%d",&n);

for(i=0;i;i++){ span="" <=""></n;i++){>

scanf("%d",&a[i]);

}

scanf("%d",&key);

low=0; // 시작값

high=n-1; // 끝값

while(low<=high){

mid=(low+high)/2; // 중간값

if(a[mid]==key){

flag=1;

break;

}

if(a[mid]) low="mid+1;</span"></key)>

else high=mid-1;

}

if(flag==1) printf("%d",mid+1);

else printf("0");

return 0;

}