이진 탐색 (Binary Search) - JAVA

이진 탐색은 데이터가 정렬되어 있는 상태에서 원하는 값을 찾아내는 알고리즘 입니다.

데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 찾는 방법입니다.

시간 복잡도는 O(log n)입니다.

 

출처 : https://commons.wikimedia.org/wiki/File:Binary_search_into_array.png

탐색 과정

• 현재 데이터에서 중앙값 선택
• 중앙값 > 탐색값 일 때 중앙 값을 기준으로 왼쪽데이터셋 선택
• 중앙값 < 탐색값 일 때 중앙 값을 기준으로 오른쪽데이터셋 선택
• 탐색값을 찾을 때까지 1 ~ 3번 과정 반복

 

구현

 

아래의 문제를 예시로 들어 이진탐색을 구현하였습니다.

1920번: 수 찾기

public class P1920_수찾기 {
	static int[] nums;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		// 초기 정보 입력
		int N = Integer.parseInt(br.readLine());
		nums = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < N; i++) {
			nums[i] = Integer.parseInt(st.nextToken());
		}
		// 이진 탐색을 위한 정렬
		Arrays.sort(nums);
		
		int M = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < M; i++) {
			int target = Integer.parseInt(st.nextToken());
			int start = 0;
			int end = N - 1;
			boolean check = false;
			while(start <= end) {
            		// 시작 index와 마지막 index를 기준으로 /2
				int mid = (start + end) / 2;
                	// mid에 있는 값보다 target 값이 작다면 mid의 왼쪽
				if(target < nums[mid])end = mid - 1;
                	// mid에 있는 값보다 target 값이 크다면 mid의 오른쪽
				else if(target > nums[mid])start = mid + 1;
                	// mid값과 target값이 같다면 종료
				else if(target == nums[mid]) {
					check = true;
					break;
				}
			}
			if(check)System.out.println(1);
			else System.out.println(0);
		}
	}
}