순차탐색은 쉬웠으니 빠르게 다음 공부할 이진탐색(Binary Search)에 대해서 알아보자.
이진탐색은 한번 비교를 할때마다 비교를 하는 범위가 반으로 줄어든다
이게 순차탐색과 비교해서 알마나 큰 차이가 있냐면
만약 70억개의 데이터를 검색했을때 순차탐색은 최대 70억 번 평균 35억 번을 비교 하는데
이진탐색은 최대 33번의 비교로 탐색을 완료 할 수가 있다.
대신 조건이 하나 있는데 이진탐색에 사용하는 배열을 정렬되어진 배열이어야 한다는 것이다.
그림으로 알아보도록 하자
먼저 배열의 중앙을 선택하고 찾고자 하는 값보다 큰지 작은지 비교를 합니다.
5는 7보다 작기 때문에 5에서 오른쪽에 있는 요소들로 이동하여
다시 그중 중앙에 위치한 값을 선택해 비교 합니다.
8은 7보다 크기 때문에 왼쪽으로 이동을 합니다
이런식으로 범위를 좁혀나가다 보면 원하는 값을 찾게 되겠죠
한번 검색을 수행할떄마다 범위가 반으로 줄어든다는 말이 이해가 되지 않는다면
노트에 펼쳐놓고 위의 그림을 따라서 그리고 검색하지 않는 범위부터 반으로 접어 보면 이해가 갈 것이다.
이진탐색의 시간 복잡도 : O(log n)
이진탐색의 구현 소스를 보면 생각보다 간단하다. 위에 그림에 있는 if문을 반복할 뿐이다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | int BinarySearch(int dataArr[], int size, int findData) { int low = 0, high = size - 1, mid; // low = 검색 할 범위의 가장 왼쪽 // high = 검색할 범위의 가장 오른쪽 // high가 low보다 작아진다면 찾으려는 데이터가 데이터 집합에 없다. while (low <= high) { // 중앙값은 low와 high를 더한 값을 2로 나누면 된다. mid = (low + high) / 2; // 만약 찾으려는 값이 중앙값보다 작다면 high를 mid - 1로 둔다. // 찾는값이 중앙값보다 작기 때문이다. // 이때 mid-1 = 다음검색할 범위의 가장 오른쪽이 된다. if (dataArr[mid] > findData) high = mid - 1; // 만약 찾으려는 값이 중앙값보다 크다면 low를 mid + 1로 둔다. // 찾는값이 중앙값보다 크기 때문이다 // 이때 mid+1 = 다음 검색할 범위의 가장 왼쪽이 된다. else if (dataArr[mid] < findData) low = mid + 1; // 중앙값과 찾으려는 값이 일치하면 mid를 반환한다. else return mid; } // 데이터를 찾지 못하면 -1를 반환한다. return -1; } int main() { int dataArr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 17, 21, 24, 26, 27, 28}; int length = sizeof dataArr / sizeof dataArr[0]; int input, ret; scanf("%d", &input); ret = BinarySearch(dataArr, length, input); // 이진탐색 실행 if (ret != -1) printf("찾으려는 데이터는 %d번째에 있습니다.\n", ret + 1); else printf("데이터를 찾을 수 없습니다.\n"); return 0; } | cs |
(참조 http://blog.eairship.kr/246)
주석이 많아서 좀 복잡해 보이는데 주석도 빼버리면
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | int BinarySearch(int dataArr[], int size, int findData) { int low = 0, high = size - 1, mid; while (low <= high) { mid = (low + high) / 2; if (dataArr[mid] > findData) high = mid - 1; else if (dataArr[mid] < findData) low = mid + 1; else return mid; } return -1; } int main() { int dataArr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 17, 21, 24, 26, 27, 28}; int length = sizeof dataArr / sizeof dataArr[0]; int input, ret; scanf("%d", &input); ret = BinarySearch(dataArr, length, input); // 이진탐색 실행 if (ret != -1) printf("찾으려는 데이터는 %d번째에 있습니다.\n", ret + 1); else printf("데이터를 찾을 수 없습니다.\n"); return 0; } | cs |
이런 소스가 된다.
생각보다 간단한 코드다.
'Yame Programmer > 자료구조&알고리즘' 카테고리의 다른 글
| 야매 개발자 자료구조 가이드[이진트리(binary)의 순회(traversal)] (0) | 2016.10.19 |
|---|---|
| 야매 개발자 자료구조 가이드[트리(tree)] (0) | 2016.10.18 |
| 야매 개발자 알고리즘 가이드[순차탐색(Sequential Search)] (0) | 2016.10.18 |
| 야매 개발자 알고리즘 퀵 정렬[Quick Sort] (6) | 2016.10.11 |