이분 탐색(Binary Search)

개념 요약

• 주어진 벡터에서 주어진 값을 찾는 방법
• 정렬이 되어있는 벡터에서 중간값을 기준으로 벡터를 나눠서 찾는다.
• 탐색 범위가 절반씩 줄기 때문에 효율적이다.

---

진행 순서

1. 주어진 벡터의 중간값을 뽑는다.
2. 중간값보다 크다면 중간값을 최솟값으로, 작다면 최댓값으로 설정하고 재귀를 시행.
3. 찾았다면 인덱스 반환

 

---

코드

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)$

---

장단점

• 주어진 벡터가 정렬되어있을 때만 사용 가능하다.
• 비교 범위를 반으로 잘라가면서 하기 때문에 효율적이다.