이분 탐색

배열이 정열되어 있다는 것은 수학적으로 단조증가 수열이라는 것과 동치입니다.

즉, x0 < x1 < ... < xn이 있을 때 어떤 값 xk를 뽑고 그 값이 내가 찾는 값보다 크다면

xk, xk+1, ... , xn-1역시 원하는 값보다 클 것입니다. 그렇다면 굳이 이 값들은 탐색할 필요가 없으므로 과감하게 제거합니다. 반대로 내가 찾는 값보다 작을 경우 x0, x1, .... , xk는 탐색할 필요가 없습니다.

public static int solution(int[] arr, int M) { // arr 배열에서 M을 찾자
	
    Arrays.sort(arr); // 정렬
	
	int start = 0; // 시작
	int end = arr[arr.length-1]; // 끝
	
	while(start <= end) {
		
		int sum = 0;
		int mid = (start+end)/2; // 시작과 끝의 중간값
		
		for (int i = 0; i < arr.length; i++) {
			if(arr[i] > mid)
				sum+=mid;
			else
				sum+=arr[i];
		}
		
		if(sum > M)
			end = mid - 1;
		else
			start = mid + 1;
		
	}
    
	return end;
}

 

while문을 이용하여 재귀 없이도 구현 가능하다는 것이 특징입니다. 이때 여겨봐야할 부분은 start > end일 떄 입니다. start = end = mid 인 경우엔 xm = x면 답을 찾은 것이므로 무사히 반환할 수 있습니다. 그러나 만약 xm 이 x와 같지 않으면 적어도 x < xm이거나 x > xm이므로 함수가 한 번 더 실행되고 start > end인 경우가 발생합니다.

따라서 이분탐색에서 주의해야할 부분은 중복이 있는 경우입니다. 키 값에 중복이 있으면 그 중 하나의 키만 반환이 되기 때문입니다. 이 사실에 유념해야할 것입니다.

시간 복잡도는 O(log N)으로 비교적 나쁘지 않은 편입니다.

 

정리하자면

 

진행 순서

• 우선 정렬을 해야 함
• left와 right로 mid 값 설정
• mid와 내가 구하고자 하는 값과 비교
• 구할 값이 mid보다 높으면 : left = mid+1 구할 값이 mid보다 낮으면 : right = mid - 1
• left > right가 될 때까지 계속 반복하기