Algorithm/개념정리
이분 탐색(Binary Seaerch) C++ / 장단점 / 시간복잡도 :: DANIDANI
DANIDANI
2021. 1. 28. 18:12
알고리즘 개념
- 정렬이 되어있는 배열에서 데이터를 찾을 때, 원하는 탐색 범위를 두 부분으로 나눠 찾아간다.
- 중간 값과 비교해서 탐색 범위를 절반씩 줄여간다.
과정
- 정렬을 한다.
- left 값과 right 값의 중간값인 mid를 정한다.
- 찾고자 한 값과 mid와 비교후, mid보다 작으면 right = mid -1, mid보다 크면 left = mid + 1로 설정한다.
- left > right가 될 때까지 반복한다.
코드
int binarysearch(int key, int left, int right){
long long mid = (left + right) / 2;
if(left <= right){
if(key == arr[mid]) return 1;
else if(key < arr[mid]) return binarysearch(key, left, mid - 1);
else return binarysearch(key, mid + 1, right);
}
else return 0;
}
장점
- 전부 탐색하는 것보다 훨씬 빠르다.
단점
- 정렬이 된 상태에서 사용이 가능하다.
시간복잡도
- O(logN)
728x90