logN
오름차순
으로 정렬된 자료여야 한다.start
: 리스트의 첫번째 원소 idxend
: 리스트의 마지막 원소 idxmid
: (start + end) // 2실행횟수
따라서 N에 따른 시행횟수는 O(logN) 으로 표기 가능def binary_search(target, data):
data.sort()
start = 0
end = len(data)-1
while start<=end:
mid = (start+end)//2
if target == data[mid]:
return mid
elif data[mid] < target:
start = mid +1
else:
end = mid-1
return None
# data는 오름차순 정렬된 데이터라고 가정
def binary_search(start, end, target, data):
if start > end:
return None
mid = (start+end) // 2
if data[mid] == target:
return data[mid]
elif data[mid] < target:
start = mid + 1
else:
end = mid - 1
return binary_search(start, end, target, data)