반응형
안녕하세요. BlockDMask 입니다.
알고리즘 코딩 사이트(백준 온라인 저지)에서 '수 찾기' 문제를 풀다가 이진탐색(Binary Search)이 나와서,
이번 기회에 정리를 해볼까 합니다.
1. 이진탐색(Binary Search) 이란.
이진 탐색 알고리즘(Binary Search Algorithm)은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘 입니다.
오름차순으로 정렬된 리스트의 중간 값을 임의의 값으로 선택하여, 찾고자 하는 Key값과 비교하는 방식으로 돌아가는 알고리즘 입니다.
정렬된 리스트에서만 사용할 수 있다는 단점이 존재합니다.
검색이 될때마다 선형탐색(Linear Search)와는 비교할 수 없게 빨라집니다.
2. 이진탐색(Binary Search)의 시간 복잡도
입니다.
3. 이진탐색(Binary Search)의 구현
이진탐색을 구현하는 방법 : 제가 알고있는 것은 세가지가 있습니다.
직접 구현 - 반복문을 이용한 이진 탐색
12345678910111213141516171819202122//반복문을 이용한 이진탐색을 이용하여 탐색bool BinarySearch(int *arr, int len, int key){int start = 0;int end = len-1;int mid;while(end - start >= 0) {mid = (start + end) / 2; //중앙 값if (arr[mid] == key) { //key값을 찾았을때return true;} else if (arr[mid] > key) { //key값이 mid의 값보다 작을때 (왼쪽으로)end = mid - 1;} else { //key값이 mid의 값보다 클때 (오른쪽으로)start = mid + 1;}}return false;}cs 직접 구현 - 재귀를 이용한 이진 탐색
123456789101112131415161718//재귀를 이용한 이진탐색을 이용하여 탐색bool BinarySearch(int *arr, int start, int end, int key) {if (start > end) return false; //key 값이 없을 때int mid = (start + end) / 2;if (arr[mid] == key) { //key 값을 찾았을 때return true;} else if (arr[mid] > key) { //key 값이 mid 의 값보다 작을때(왼쪽으로)return BinarySearch(arr, start, mid - 1, key);} else { //key 값이 mid 의 값보다 작을때(왼쪽으로)return BinarySearch(arr, mid + 1, end, key);}}cs STL이용 - binary_search 함수를 이용한 이진 탐색
<algorithm> 해더 파일안에 있는 binary_search 함수를 이용하면 됩니다.
binary_search 의 기본형은 이러합니다.
1 2 | template <class ForwardIterator, class T> bool binary_search (ForwardIterator first, ForwardIterator last, const T& val) | cs |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | #include<iostream> #include<algorithm> using namespace std; //STL를 이용한 이진탐색을 이용하여 탐색 int main(void){ int n= 100; int arr[n]; for(int i=0; i<n; i++){ arr[i] = i; } cout << "exist : " << binary_search(arr, arr+n, 70) << endl; return 0; } | cs |
반응형
'<개인공부> > [Algorithm]' 카테고리의 다른 글
퀵 정렬 (Quick Sort) 이론과 코드 (3) | 2017.10.19 |
---|---|
[탐색] lower_bound, upper_bound (5) | 2017.10.11 |
[알고리즘의 정의] Algorithm? (0) | 2017.10.07 |
선택 정렬 (Selection Sort) 이론과 코드 (3) | 2017.09.24 |
삽입정렬 (Insertion Sort) 이론과 코드 (0) | 2017.08.05 |
버블정렬 (Bubble Sort) 이론과 코드 (2) | 2017.07.31 |
[유클리드 알고리즘] GCD 최대공약수 (반복문, 재귀) (4) | 2017.07.14 |