이진탐색

이진탐색 순서

초기화

• 데이터가 정렬되어 있어야 한다.
• 탐색 범위를 나타내는 두 포인터(low, high)를 지정해야 한다.

중간 값 계산

• 현재 탐색 범위의 중간 값을 계산한다
• 중간 값(middle)과 찾고자 하는(target)의 값을 비교 한다.

값 비교 및 탐색 범위 축소

• 중간 값이 찾고자 하는 값과 같으면 종료
• 중간 값이 찾고자 하는 값보다 작으면 Low를 중간 값 보다 하나 크게 해서 올린다.
  • low = middle + 1
• 중간 값이 찾고자 하는 값보다 크면 High를 중간 값 보다 하나 작게 해서 내린다.
  • high = middle - 1

반복

• 위 과정을 low가 high보다 커질때 까지 반복한다.

while(low <= high) {
	...
}

시간 복잡도

O(logn)

중요 포인트

탐색 범위 지정

이진 탐색 문제를 풀 때 가장 중요한 부분은 어떤 값을 이진 탐색의 대상(탐색 범위)으로 설정하여 문제를 해결할지 파악하는 것이다. 문제를 봤을 때 알아 채기 쉬운 부분도 있지만 그렇지 않은 경우도 있다.

문제 예시

백준 문제 해당 문제는 공유기를 배치할 때 최적의 위치를 찾는 문제였다.
처음에는 어떻게 접근해야 할 지 감을 찾지 못하였었다.
이 문제에서 이진 탐색으로 접근 할 때 신경써야 할 점은 길이가 조정이 될 때 배치 될 수 있는 공유기의 갯수를 확인하는 문제였다.
추후 이진탐색으로 판단 되는 문제가 있다면 원하는 답이 이진탐색으로 조정된다고 가정하고 이진탐색의 기준점이 변했을 때 기준점이 어떻게 변하는 지 접근해 볼 필요가 있어 보인다.

최적의 해를 찾을 때 조건을 잘 살펴본다

백준 문제

놓친 부분

문제를 풀 때 이진 탐색을 적용한 다음에 현재 중간 값(middle)시점에서 최대의 예산을 찾는 방식으로 진행하였다. 여기서 놓친 부분이 예산을 넘길 경우에는 해당 조건을 만족하지 않는 경우로 판단되어서 맞는 답으로 진행하면 안됐었는데 이를 진행해서 틀린 경우이다.

코드

int currentMaxBudget = 0;
while (minBudget <= maxBudget) {
	int middleBudget = (minBudget + maxBudget) / 2;
	int sum = 0;
	currentMaxBudget = -1;
	for (int requestBudget : requestBudgetList) {
		//순차적으로 돌면서 비교를 한다.
		if (requestBudget > middleBudget) {
			sum += middleBudget;
			currentMaxBudget = Math.max(middleBudget, currentMaxBudget);
		} else {
			sum += requestBudget;
			currentMaxBudget = Math.max(requestBudget, currentMaxBudget);
		}
	}
    if (budget < sum) {
	    // 이 경우에는 예산을 초과 하는 경우이기 때문에 정답이 갱신이 되면 안된다.
		maxBudget = middleBudget - 1;
	} else if (budget == sum) {
		break;
	} else {
		minBudget = middleBudget + 1;
	}
}
 
// currentMaxBudget 출력

수정 부분

정답을 저장하는 currentMaxBudget값을 통합해서 관리하지 않고 별도로 관리해서 조건을 만족하는 경우에는 답을 갱신하도록 수정하였다.

int answer = 0;  
while (minBudget <= maxBudget) {  
	int middleBudget = (minBudget + maxBudget) / 2;  
	int sum = 0;  
	// while문 내의 지역변수로 수정
	int currentMaxBudget = -1;  
	for (int requestBudget : requestBudgetList) {  
		//순차적으로 돌면서 비교를 한다.  
		if (requestBudget > middleBudget) {  
			sum += middleBudget;  
			currentMaxBudget = Math.max(middleBudget, currentMaxBudget);  
		} else {  
			sum += requestBudget;  
			currentMaxBudget = Math.max(requestBudget, currentMaxBudget);  
		}  
	}  
 
	if (budget < sum) {  
		// 이 경우에는 예산 초과이므로 아무 계산도 하지 않는다.
		maxBudget = middleBudget - 1;  
	} else {  
		// 이렇게 참인 경우에만 정답을 갱신해준다
		answer = Math.max(answer, currentMaxBudget);  
		minBudget = middleBudget + 1;  
	}  
}
 
// answer 출력

배열 내부에서 검색을 한다

문제 링크 두 수의 합이 배열 내부에 존재하는 지 찾는 문제였다.
처음에는 반복문을 최소한으로 돌리고 싶어서 Map 자료구조를 이용해서 처음 input을 입력 받을 때
미리 저장해서 조회를 하려고 하였는데 Key의 데이터가 너무 복잡해 지는 것을 알게 되었다.
이진 탐색의 시간 복잡도는 O(logn)이고 입력값은 2000이므로 O(nlogn)으로 충분히 해결될 수 있을 것이라 판단이 된다.
여기서 생각할 것은 시간 복잡도에 대해 좀 더 상세하고 고민을 해서 접근해보자.

주요 접근 코드

for (int index = 1; index < store.length; index++) {  
	int left = 0;  
	int right = store.length - 1;  
	while (left < right) {  
		long leftData = store[left];  
		long rightData = store[right];  
 
		... // 이진 탐색 로직
	}  
 
}