def search(nums, target):
start = 0
end = len(nums)-1
while start <= end:
center = (start+end)//2
if nums[center] == target:
return center
elif nums[center] > target:
end = center-1
else:
start = center+1
return -1
def binary_search_recursion(target, start, end, data):
if start > end:
return None
mid = (start + end) // 2
if data[mid] == target:
return mid
elif data[mid] > target:
end = mid - 1
else:
start = mid + 1
return binary_search_recursion(target, start, end, data)
if __name__ == '__main__': # 메인 함수 선언
my_list = [i*3 for i in range(11)]
target = 9
my_index = binary_search_recursion(target, 0, 10, my_list)
print(my_list)
print(my_index)
이진탐색법의 시간 복잡도
- 처음에 데이터 수가 n개일 때의 탐색과정에서 1회의 비교연산 진행
- 데이터 수를 반으로 줄여서 그 수가 n/2개일 때의 탐색과정에서 1회 비교연산 진행
- 데이터 수를 반으로 줄여서 그 수가 n/4개일 때의 탐색과정에서 1회 비교연산 진행
- 데이터 수를 반으로 줄여서 그 수가 n/8개일 때의 탐색과정에서 1회 비교연산 진행
..........- 데이터 수를 반으로 줄여서 그 수가 1개일 때의 탐색과정에서 1회 비교연산 진행
-> n이 1이 되기까지 2로 나눈횟누는 k회
-> 데이터가 1개 남았을 때, 마지막으로 비교연산을 진행해서 1회 진행
->
->
->
->
- 시간복잡도 :
-> 1은 생략 가능
->