[공유] 이진탐색

출처 오분쯤 느린 시계|영양 앞서 순차 탐색에 대해 간단하게 알아 보았는데 탐색 속도가 만족할만한 수준이 아니었다. 그러므로 이번에는 평균 탐색 속도가 순차 탐색에 비해 월등히 좋은 이진 탐색에 대해 알아보도록 하겠다. 이진 탐색은 기본적으로 데이터가 정렬되어 있는 상태여야 한다. 데이터가 정렬 되어 있다면 탐색시에 상당히 효율적으로 이용할 수 있다. 이진 탐색에서는 정렬된 데이터의 범위를 1/2, 1/4, 1/8, ... 이런 방식으로 찾는 범주를 반씩 줄여 나간다. 찾는 위치의 데이터가 찾고자하는 값보다 작을 경우 그 바로 이전 위치까지가 다음에 찾게될 범주의 끝이 되고, 클 경우 그 위치의 다음 위치가 다음에 찾게될 범주의 시작이 되며, 같을 경우는 탐색을 중단하게 된다. 결국 이진 탐색을 이용할 경우의 시간 복잡도는 log n을 따르게 된다. 아래는 이진 탐색을 간략하게 표현한 그림이다. 이진 탐색 이진 탐색 방법은 이전에 포스팅했던 순차 탐색에 비해 탐색 성능면에서 상당히 ...

원문링크 : [공유] 이진탐색