재귀함수로 이진 탐색을 구현한 코드. 리스트의 절반에 위치한 요소와
검색하는 값을 비교한 뒤 리스트 슬라이싱을 하고 나서 재귀함수를 호출한다.
그렇게 되면, 리스트의 크기는 절반씩 타노스(?) 당할 것이고 결국엔 찾고자 하는 값을 발견하면 true를 리턴하는 코드이다.
def binary_search(data,search):
if len(data)==1 and search == data[0]:
return True
if len(data)==1 and search!=data[0]:
return false
if len(data)==0:
return false
medium = len(data)//2
if search == data[medium]:
return True
else:
if search>data[medium]:
return binary_search(data[medium:],search)
else:
return binary_search(data[:medium],search)
n개의 리스트를 매번 2로 나누어 1이 될 때까지 비교 연산을 k회진행
결국 O(log2n+1)이고, 2와1, 상수는 삭제되므로, O(logn)