[C++] 이진 검색 구현
자료구조이진 검색 알고리즘은 정렬된 리스트에서 특정한 값의 위치를 찾기위해 찾을 값과 현재 유효한 값의 범위의 중간값을 비교해 범위를 좁히는 식으로 검색하여 빠르게 목표값을 찾을 수 있는 장점이 있다.
1 2 3 4 5 6 7 8 9 10 11 12 | int binarySearch(int arr[], int size, int find) { int low=0, high=size-1, mid; while(low<=high) { mid = (low+high)/2; if(arr[mid] > find) high = mid - 1; else if(arr[mid] < find) low = mid + 1; else return mid; } return -1; } |
#4 low가 high보다 커진다면 찾으려는 데이터가 없다는 것이다.
#11 목표값이 없을 경우에는 -1을 리턴해 준다.
'자료구조' 카테고리의 다른 글
| [C++] Bubble Sort 구현 (0) | 2015.11.12 |
|---|---|
| [C++] 간단한 Queue 만들기 (0) | 2015.11.12 |
| [C++] 간단한 Stack 만들기 (0) | 2015.11.11 |