-
Notifications
You must be signed in to change notification settings - Fork 0
/
재귀함수로구현한이진탐색.py
36 lines (30 loc) · 970 Bytes
/
재귀함수로구현한이진탐색.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# 이진탐색
# 재귀함수로 구현
def recursive_binary_search(array, target, start, end):
if start > end:
return None
mid = (start+end) // 2
if array[mid] == target:
return mid
elif array[mid] > target:
return recursive_binary_search(array, target, start, mid-1)
else:
return recursive_binary_search(array, target, mid+1, end)
def iterative_binary_search(array, target, start, end):
while start <= end:
mid = (start+end) // 2
if array[mid] == target:
return mid
elif array[mid] > target:
end = mid - 1
else:
start = mid + 1
return None
n, target = list(map(int, input().split()))
array = list(map(int, input().split()))
result = recursive_binary_search(array, target, 0, n-1)
# result = iterative_binary_search(array, target, 0, n-1)
if result == None:
print("원소가 존재하지 않습니다.")
else:
print(result + 1)