앞서 순차 탐색에 대해 간단하게 알아 보았는데 탐색 속도가 만족할만한 수준이 아니었다.
그러므로 이번에는 평균 탐색 속도가 순차 탐색에 비해 월등히 좋은 이진 탐색에 대해 알아보도록 하겠다.
이진 탐색은 기본적으로 데이터가 정렬되어 있는 상태여야 한다.
데이터가 정렬 되어 있다면 탐색시에 상당히 효율적으로 이용할 수 있다.
이진 탐색에서는 정렬된 데이터의 범위를 1/2, 1/4, 1/8, ... 이런 방식으로 찾는 범주를 반씩 줄여 나간다.
찾는 위치의 데이터가 찾고자하는 값보다 작을 경우 그 바로 이전 위치까지가 다음에 찾게될 범주의 끝이 되고, 클 경우 그 위치의 다음 위치가 다음에 찾게될 범주의 시작이 되며, 같을 경우는 탐색을 중단하게 된다.
결국 이진 탐색을 이용할 경우의 시간 복잡도는 log n을 따르게 된다.
아래는 이진 탐색을 간략하게 표현한 그림이다.
이진 탐색
하지만 이진 탐색을 위해서는 미리 정렬이 되어있어야 한다는 것을 염두해 두어야한다.
아래에는 이진 탐색에 대한 소스코드를 첨부하였다.
소스코드에는 이진 탐색을 위한 정렬 방법으로 선택 정렬을 사용하였다.
Search_binary.c[자료구조와 알고리즘] - 순차 탐색(Sequential Search)
TRACKBACK 0 AND
COMMENT 1
PREV
