7276 : 재귀 이진탐색
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
이진 탐색을 재귀 함수로 구현하십시오.
반복문(while) 없이 재귀 호출만으로 탐색해야 합니다.
재귀 원리: 중간값이 타겟이면 반환, 작으면 오른쪽 탐색, 크면 왼쪽 탐색입니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
반복문(while) 없이 재귀 호출만으로 탐색해야 합니다.
재귀 원리: 중간값이 타겟이면 반환, 작으면 오른쪽 탐색, 크면 왼쪽 탐색입니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 배열의 크기 $N$과 찾고자 하는 수 $X$가 주어집니다.
둘째 줄에 오름차순 정렬된 $N$개의 정수가 주어집니다.
둘째 줄에 오름차순 정렬된 $N$개의 정수가 주어집니다.
출력 설명
$X$의 인덱스(0-based)를 출력합니다. 없으면
-1을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
7 7
1 3 5 7 9 11 13
출력 예시
COPY
복사되었습니다!
복사되었습니다!
3도움
def binary_search(arr, lo, hi, x): if lo > hi: return -1; mid=(lo+hi)//2; if arr[mid]==x: return mid; elif arr[mid]<x: return binary_search(arr,mid+1,hi,x); else: return binary_search(arr,lo,mid-1,x)