P1446 - 재귀호출로 이진 탐색 구현하기

메모리제한：128 MB 시간제한：1.000 S

Judge Style：Text Compare 만든사람：

제출：2 통과：0

제출 채점 기록 통계 묻고답하기

n개의 데이터가 있을 때, 특정 데이터가 어떤 위치에 있는지 찾는 것이 문제이다.

이 특정 데이터를 찾는 방법의 가장 기본적인 방법으로는 데이터를 처음부터 끝까지 차례대로 찾는 순차(선형)탐색과

데이터들의 중앙 값을 기준으로 하여 탐색 범위를 반 씩 줄여나가는 이진탐색이 있다.

재귀 호출을 이용하여 탐색을 구현해보자.

[미리 작성된 프로그램] - C/C++로 제출하는 경우에만 추가됩니다.

#include <stdio.h>

int arr[100001] = {0,};
int i = 0;

int d_input(int max){
if(max>0){
    scanf("%d", &arr[i++]);
  d_input(max-1);
  }
}

int do_search(int list[], int key, int low, int high){
  //여기 들어갈 부분을 채우시오.
}

int main(){
  int num, search;

  scanf("%d", &num);

  d_input(num);

  scanf("%d", &search);

  printf("%d", do_search(arr, search, 0, num-1));
}

※ JAVA/Python으로 제출시 위 코드가 추가되지 않습니다.

첫째 줄에 데이터의 개수 n이 입력된다.(1 <= n <= 100,000)

둘째 줄에 n개의 양의 정수 데이터가 공백으로 분리되어 입력된다.

셋째 줄에 찾고자 하는 특정데이터 정수 k 가 입력된다.

k를 찾았으면 데이터 k의 위치를 출력하고, 찾지 못했으면 -1을 출력한다.

10
2 3 4 7 9 10 23 39 111 223
111

탐색 재귀

1446: 재귀호출로 이진 탐색 구현하기

문제 설명

입력 설명

출력 설명

입력 예시 Copy

출력 예시 Copy

출처/분류