파이썬으로 이진 탐색 구현하기

이진 탐색(binary search)은 정렬된 데이터에서 특정한 값을 아주 빠르게 찾는 방법이다. N개의 데이터 중에서 특정한 값 x를 찾을 때, 최악의 경우 N번의 비교가 필요한데, 이진 탐색의 경우 최대 log_{2}N만큼의 비교를 하게 된다. 즉 자료의 크기가 클수록 선형 탐색에 비해 성능이 매우 우수해진다. 다만 이진 탐색은 자료가 정렬되어 있다는 전제가 필요하다. (이 때문에 컴퓨터 과학에서는 정렬이 매우 중요하고, 성능이 좋은 정렬 알고리듬을 만들기 위해 많은 노력이 있어왔다.)

파이썬으로 이진 탐색 구현하기 더보기