개념 요약
- 주어진 벡터에서 주어진 값을 찾는 방법
- 정렬이 되어있는 벡터에서 중간값을 기준으로 벡터를 나눠서 찾는다.
- 탐색 범위가 절반씩 줄기 때문에 효율적이다.
진행 순서
- 주어진 벡터의 중간값을 뽑는다.
- 중간값보다 크다면 중간값을 최솟값으로, 작다면 최댓값으로 설정하고 재귀를 시행.
- 찾았다면 인덱스 반환
코드
int binary_search(const std::vector<int> &vec, const int &num, const int start, const int last)
{
// 처음 인덱스보다 마지막인덱스보다 크다면 없음
if (start > last)
return (-1);
// 중간값 인덱스 저장
int mid = (start + last) / 2;
// 중간값이 주어진 숫자와 같다면 인덱스 리턴
if (vec[mid] == num)
return (mid);
// 중간값이 주어진 숫자보다 크다면 시작 인덱스 조정
else if (vec[mid] < num)
return (binary_search(vec, num, mid + 1, last));
// 중간값이 주어진 숫자보다 작다면 마지막 인덱스 조정
else
return (binary_search(vec, num, start, mid - 1));
}
시간 복잡도
- $O(log_2 n)$
장단점
- 주어진 벡터가 정렬되어있을 때만 사용 가능하다.
- 비교 범위를 반으로 잘라가면서 하기 때문에 효율적이다.
'CS공부 > Algorithm' 카테고리의 다른 글
DFS & BFS (0) | 2022.06.29 |
---|---|
해시 테이블(Hash Table) (0) | 2022.06.23 |
계수 정렬(Counting Sort) (0) | 2022.06.22 |
기수 정렬(Radix Sort) (0) | 2022.06.22 |
힙 정렬(Heap Sort) (0) | 2022.06.21 |