Menu

Subscribe

[JAVA/백준] 이분 탐색: 수 찾기

HEESOO on Boj

👀 문제

https://www.acmicpc.net/problem/1920

👊 도전

1. 설계

  1. n개의 정수를 array에 저장한 후, 이분 탐색을 위해 오름차순 정렬한다.
  2. m개의 수는 input에 저장하여 이분 탐색을 통해 array에 값이 있는지 확인한다.

2. 구현 (성공 코드)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author HEESOO
 *
 */
public class Main {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scan = new Scanner(System.in);
		int n=scan.nextInt();
		int[] array=new int[n];
		for(int i=0;i<n;i++)
			array[i]=scan.nextInt();
		Arrays.sort(array);
		
		int m=scan.nextInt();
		int[] input=new int[m];
		for(int i=0;i<m;i++)
			input[i]=scan.nextInt();
		
		for(int i=0;i<m;i++) {
			int first=0;
			int last=n-1;
			int mid=0;
			while(first<=last) {
				mid=(first+last)/2;
				if(input[i]==array[mid]) {
					System.out.println("1");
					break;
				}
				else {
					if(input[i]<=array[mid]) 
						last=mid-1;
					else
						first=mid+1;
				}
			}
			if(first>last)
				System.out.println("0");
		}
	}
}

3. 결과

실행결과 🤟 성공 🤟

4. 설명

  1. 이분 탐색을 사용한다
    • 이분탐색을 사용하기 위해서는 정렬된 오름차순이어야 한다. 따라서 array를 오름차순으로 정렬한다.
    • m개의 정수를 input 배열에 저장하고, for문을 이용해 하나씩 순회한다.
    • for문안에서 while문을 돌려 이분탐색을 진행한다. 이분탐색은 시작 인덱스 first와 마지막 인덱스 last를 반씩 줄여가면서 진행한다. 둘이 만나면 while문을 종료한다. while문이 끝날 때 까지 1을 출력하지 못한다면 input[i]가 없다는 뜻이므로 0을 출력한다.
    • first와 last의 중간 인덱스인 mid를 구한 후, array[mid]가 input[i]와 같다면 1을 출력한다.
    • input[i]가 array[mid]보다 작다면 last를 조정하여 범위를 줄이고, 크다면 first를 조정한다.

👏 해결 완료!