개요

최장증가부분수열에 대해 공부하다가 이분탐색이 필요하게 되어 익히게 됐다.

특징

보통 선형탐색의 경우 O(N)이지만

이진 탐색은 계속 반씩 나누어 나머지 한쪽은 버리는 사이클을 이용하여 탐색을 진행하기 때문에

O(log N)으로 탐색이 가능하다.

단 단점은 정렬된 컨테이너에서만 가능하다.

또한 정확히 반으로 나누지 않을 경우 무한 루프에 빠지는 경우가 있다.

왜 사용하는가?

선형 탐색보다 빠른 속도로 탐색을 진행하려고!

구현

Binary search

int BinarySearch(const int * arr, const int & size, const int & f)
{
	int s = 0, e = size, m;

	while (s <= e)
	{
		m = (s + e) / 2;

		//중앙 값이 찾는 값인지 확인
		if (arr[m] == f) return m;

		//시작 or 끝 인덱스 조정
		if (arr[m] < f) s = m + 1;
		else e = m - 1;
	}
	return -1;
}

시작 인덱스(s), 중앙 인덱스(m), 끝 인덱스(e) 를 의미하는 정수형 변수로 돌아가게 된다.

m은 항상 (s + e) / 2 로 구할 수 있고

m이 찾는 값보다 크다면 끝 지점을 m으로 옮기고

m이 찾는 값보다 작다면 시작 지점을 m으로 옮긴다.

이렇게 진행하다보면 어느 순간 s와 e가 겹치게 되는데

이때 끝내버리면 m이 s와 e가 겹친 인덱스를 한번도 찾지 못하게 되어서

while ( s < e ) 가 아닌 while ( s <= e ) 를 사용했다.

그 후 교차가 되어서 교차가 되면 끝나고 찾지 못했다는 의미로 -1을 반환하는 형식으로 구현했다.

개요

이분 탐색문제를 풀이하다 나온 개념

특징

이분 탐색을 응용한 알고리즘으로

정렬된 수열에서 찾고자 하는 값들의의 첫인덱스, 마지막 인덱스 + 1 을 구할 수 있다.

왜 사용하는가?

경험상 적절한 위치를 알기 위해서 사용하는 것 같다.

Lower bound는 찾고자 하는 값 이상의 부분수열에서 첫번째 인덱스

Upper bound는 찾고자 하는 값을 초과하는 부분수열에 첫번째 인덱스

이 위치들의 특징은 이곳에 찾고자 하는 값을 삽입해도 오름차순이 유지되는 특징이있다.

그리고 Upper bound -  Lower bound 의 값은 그 안에 속한 원소의 개수도 구할 수 있다.

구현

Lower bound

int Lower_bound(const int * arr, const int & size, const int & f)
{
	int s = 0, e = size, m;
	while (s < e)
	{
		m = (s + e) / 2;

		if (f <= arr[m]) e = m;
		else s = m + 1;
	}

	return s;
}

Lower bound는 f 가 시작 되는 지점을 찾는게 목표이다.

고로

시작지점은 arr[s] <= f, 끝 지점은 f <= arr[e] 라는 조건이 붙는다.

f <= arr[m] 일때 이 조건과 같은 e를 m에 두고 

나머지 경우인 arr[m] < f 는 해당되는 s를 m의 위치에 두되,

그냥 두면 s가 f에 도달하지 못하므로 m + 1인 인덱스를 s에 부여해준다.

Upper bound

int Upper_bound(const int * arr, const int & size, const int & f)
{
	int s = 0, e = size, m;
	while (s < e)
	{
		m = (s + e) / 2;

		if (f < arr[m]) e = m;
		else s = m + 1;
	}

	return e;
}

Upper bound는 f 가 끝나는 지점 + 1 을 찾는게 목표이다.

고로

시작지점은 arr[s] <= f, 끝 지점은 f < arr[e] 라는 조건이 붙는다.

f < arr[m] 일때 이 조건과 같은 e를 m에 둔다면 f와 arr[e]는 같은 값이 될수 없으며

나머지 경우인 arr[m] <= f 는 위으 Lower bound와 같다.