[종만북] 성형 전 사진 찾기 - 이진탐색(Binary Search) JAVA

출처 : 4.3 선형 이하 시간 알고리즘 - 성형 전 사진 찾기

코드설명

일반적인 이진탐색 코드입니다.

 

흥미로운 점은, 이진탐색(Binary Search)의 숫자를 찾는 과정이 배열 A[]에서 x를 삽입할 수 있는 위치 중 가장 앞에 있는 것을 반환하다고 생각하라는 것 입니다.

 

이렇게 생각한다면, 단순히 어떤 값을 찾는게 아니라 위와 같이 사고를 함으로써 좀 더 이진탐색의 구현이 편해지는 듯한 느낌이 듭니다.

 

가장 생각해야할점은 left와 right의 차이가 항상 left + 1 < right 로써 항상 2의 차이가 존재합니다.

만약 while문에 들어갔다면 left와 right간의 거리는 항상 2 이상이라는 것을 알 수 있습니다. 이를 통해 만약 둘의 사이 거리가 1개 이하로 좁아진다면, 그떄 right를 반환한다면 우리가 원하는 값, target을 찾을 수 있습니다.

테스트케이스

처음에 사진의 개수 N, 이전과 달라진 사진의 위치(M)을 찾습니다.

입력 예시1

30 25
6 9 14 15 18 23 25 28 31 33 37 38 42 44 45 52 54 57 59 63 67 69 71 73 76 82 85 88 92 97

결과 예시 1

25

코드

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	public static int N, M;
	public static int answer = 0;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		
		N = Integer.parseInt(st.nextToken());
		int[] num = new int[N];
		int target = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<N;i++) {
			num[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(num);
		answer = binarySearch(num, target);
		System.out.println(answer);
	}
	
	public static int binarySearch(int[] A, int target) {
		int left = 0, right = N;
		
		while(left <= right) {
			int middle = (left + right ) / 2;
			
			
			if(A[middle] <= target ) {
				left = middle + 1;
			} else if(A[middle] > target) {
				right = middle - 1;
			}
			
		}
		return A[right];
	}
	
}

 

불변식 활용하여 증명하며 진행합니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, M;
	public static int answer = Integer.MAX_VALUE;
	public static int[] arr;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		arr = new int[N];
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<N;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(arr);
		System.out.println(binarySearch(M));
	}
	
	//필수 조건 : A는 오름차순으로 정렬되어 있다.
	//결과 : A[i-1] < x <= A[i]인 i를 반환한다.
	//이때 A[-1] = 음의 무한대, A[arr.length, 즉 N] = 양의 무한대 라고 가정한다.
	public static int binarySearch(int target) {
		int left = -1, right = arr.length;
		
		//반복문 불변식 1 : left < right
		//반복문 불변식 2 : A[left] < target <= A[right]
		// (*) 불변식은 여기서 성립해야 한다.
		while(left + 1 < right) {
			int middle = (left + right) / 2;
			if(arr[middle] < target) {
				left = middle;
			} else if(arr[middle] >= target) {
				right = middle;
			}
			// (**) 불변식은 여기서도 성립해야 한다.
		}
		
		return right;
	}
	
	
}