[파이썬 자료구조] 이진탐색(binary search)

이진탐색 

data: 리스트 e: 찾고자하는 원소 l: 리스트의 첫 인덱스 h: 리스트의 마지막 인덱스

시간복잡도

이진탐색의 수행시간을 알아보자

전체 리스트길이를 계속 반으로 나눠서 재귀적으로 수행하고 한번씩 비교를 한다.

리스트를 이진트리로 구현했을 때 최악의 경우 트리의 높이인 log(n)만큼 수행함 

따라서 시간복잡도는 O(log(n))이다.