[JAVA] 이분탐색 (백준 1920)

이분 탐색 (Binary Search)

정렬된 배열 또는 리스트에서 원하는 값을 찾는데 사용되는 알고리즘 중 하나로, 배열이나 리스트가 정렬되어있다는 조건이 필요하다. 알고리즘의 핵심은 중간 값을 선택하고, 찾고자 하는 값과 중간값을 비교하여 탐색 범위를 반으로 줄여가는 것이다.

기본적인 동작은 다음과 같다.

1. 시작점과 끝점을 설정 : 정렬된 배열이나 리스트에서 탐색 범위의 시작점과 끝점을 설정한다.
2. 중간 값 찾기 : 시작점과 끝점의 중간에 해당하는 인덱스를 찾는다.
3. 중간 값 비교 : 중간값과 찾고자 하는 값을 비교한다
• 중간 값이 찾고자하는 값과 같았다면, 찾은 것이다.
• 중간 값이 찾고자 하는 값보다 크다면, 큰 점을 주간 값의 이전 인텍스로 설정하여 범위를 반으로 줄인다.
• 중간 값이 찾고자 하는 값보다 작다면, 시작점을 중간 값의 다음 인덱스로 설정하여 범위를 반으로 줄인다.
4. 반복 : 원하는 값이 나올 때까지 위의 과정을 반복한다.

예시

public class BinarySearch {
    public static int binarySearch(int[] array, int target) {
        int left = 0;
        int right = array.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (array[mid] == target) {
                return mid; // 원하는 값 발견
            } else if (array[mid] < target) {
                left = mid + 1; // 중간값보다 큰 부분 탐색
            } else {
                right = mid - 1; // 중간값보다 작은 부분 탐색
            }
        }

        return -1; // 원하는 값이 없음
    }

    public static void main(String[] args) {
        int[] sortedArray = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int targetValue = 7;

        int result = binarySearch(sortedArray, targetValue);

        if (result != -1) {
            System.out.println("원하는 값 " + targetValue + "의 인덱스: " + result);
        } else {
            System.out.println("원하는 값 " + targetValue + "을 찾을 수 없습니다.");
        }
    }
}

수 찾기 (백준 1920)

위의 이분탐색 알고리즘을 바탕으로 풀이해본다.

-> 백준 1920 수 찾기

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

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[] base = new int[N];
        String[] str = br.readLine().split(" ");
        for(int i = 0; i < N; i++){
            base[i] = Integer.parseInt(str[i]);
        }

        Arrays.sort(base);

        int M = Integer.parseInt(br.readLine());
        String[] str1 = br.readLine().split(" ");

        StringBuilder sb = new StringBuilder();

        for(int i = 0; i < M; i++){
            int target = Integer.parseInt(str1[i]);
            int result = isTrue(base, target);
            sb.append(result).append("\n");
        }

        System.out.print(sb.toString());
    }

    private static int isTrue(int[] base, int target){
        int start = 0; int end = base.length -1;

        while(start <= end){
            int mid = (start + end ) / 2;   //중앙 값
            if(base[mid] == target){
                return 1;
            }else if(base[mid] > target){
                end = mid -1;
            }else{
                start = mid + 1;
            }
        }
        
        return 0;
    }
}