이진 검색

프로그램 명: binary_search

제한시간: 1 초

아래 나타난 C 프로그램은 감소하지 않는 순서로 (nondescending) 정렬된 배열에서 정수 x를 이진 검색으로 찾는다.

#define MAXN 10000

int A[MAXN];
int N;

void BinarySearch(int x)
{
  int p, q, i, L;

  p = 0;   /* Left border of the search  */
  q = N-1; /* Right border of the search */
  L = 0;   /* Comparison counter         */
  while (p <= q) {
    i = (p + q) / 2;
    ++L;
    if (A[i] == x) {
      printf("Found item i = %d in L = %d comparisons\n", i, L);
      return;
    }
    if (x < A[i])
      q = i - 1;
    else
      p = i + 1;
  }
}

위의 프로그램에서 함수 BinarySearch를 호출하기 전에 1에서 10000 사이의 어떤 정수 N과 감소하지 않는 정수 순열로 채워진 행렬 A가 설정된다. 위의 함수는 값 i 와 L 을 찾은 후 "Found item i = XXX in L = XXX comparisons"라는 메시지를 출력하며 종료된다.

당신이 할 일은 주어진 i 와 L 이 나오는 것이 가능한 N 값을 모두 찾는 것이다. 하지만 가능한 N 값의 개수가 너무 많을 수 있기 때문에 가능한 N 값들을 연속한 구간들로 나누어서 각각의 구간들에 대해 첫 수와 끝 수를 출력한다.

입력

두 개의 정수 i (0 <= i < 10000) 와 L (1 <= L <= 14) 가 공백으로 구분되어 한 줄로 입력된다.

출력

첫 번째 줄에는 가능한 정수 N 들의 구간 개수 K 를 출력한다.
그리고 K 줄에 걸쳐서 증가하는 순서로 N 값의 구간을 출력한다. (각 줄에는 각 구간의 첫 수와 끝 수 A 와 B 가 (A <= B) 공백으로 구분되어 출력된다.)

입출력 예시

입출력 예시 보충

3번의 이진 검색을 통해 A[10]을 찾기 위한 처음 상한 숫자를 찾는 것이다. (A[0]~A[9999] 구간) N은 12, 17, 18, 29, 30, 87, 88, 89, 90, 91, 92, 93, 94 의 경우가 가능하다. (이진 검색은 (0,N-1) 부터 시작) 몇 가지 경우에 대해 직접 (p,q / i)를 계산하며 과정을 따라가면

(0,11 / 5)->(6,11 / 8)->(9,11 / 10)->가운데 수 10 // 3번의 이진 검색 OK
(0,28 / 14)->(0,13 / 6)->(7,13 / 10)->가운데 수 10 // 3번의 이진 검색 OK
(0,40 / 20)->(0,19 / 9)->(10,19 / 14)->(10,13 / 11)->(10,10 / 10)->가운데 수 10 // 5번의 이진 검색 NO

번역: KangJ
출처: 2000-2001 ACM Northeastern European Regional Programming Contest Problem E

[질/답] [제출 현황] [푼 후(0)]

[ 채 점 ] [홈으로] [뒤 로]