1240: 제곱근

연습문제1) 10개의 데이터를 작은 순에서 큰 순으로 입력받고 찾고자 하는 데이터 1개를 입력 받아서 10개의 데이터안에 그 데이터가 있다면 해당 번지를 출력하고 없다면 -1을 출력하는 프로그램을 작성하시오.(단,이진탐색을 활용해서 찾으시오)

 

입력예)

10 20 30 40 50 60 70 80 90 100

50

 

출력예)

4

 

int f(int arr[],int s,int e,int val){

  while(s<e){

     int mid = (s+e)/2;

     if(arr[mid] == val) return mid;

     if(arr[mid]<val) s=mid+1;

     else e = mid-1;

  }

  return -1;

}

 

 

연습문제2) 10개의 데이터를 작은순에서 큰 순으로 입력받고 찾고자 하는 데이터 1개를 입력 받아서 10개의 데이터 안에 그 데이터보다 크거나 같은 데이터 위치를 출력하는 프로그램을 작성하시오.(단, 찾고자 하는 데이터는 입력받은 10개의 데이터중 가장 큰값보다는 작거나 같은 수이다. 이진탐색을 활용해서 찾으시오.)

입력예)

10 20 30 40 50 60 70 80 90 100

55

 

출력예)

5

 

while(1){

   mid = (s+e)/2;

   if(mid == s) return e;

   if(arr[mid]<val) s=mid;

   else e = mid;

}

 

연습문제3) n 을 입력 받아 a * a 가 n 보다 커지거나 같은 수 중에 가장 작은 a 를 출력하시오.

입력 예) 101

출력예) 11

s=1;

e = n;

while(1){

   mid = (s+e)/2;

   if(mid == s) return e;

   if(mid * mid <n) s=mid;

   else e = mid;

}