[알고리즘] 백준 1920 수 찾기 - 이분탐색 - 자바

www.acmicpc.net/problem/1920

1920번: 수 찾기

 

 

 

백준 1920 수 찾기 이분탐색 단계별 풀기 첫번째 문제를 풀어봤습니다. 

 

말 그대로 이분탐색의 가장 기초적인 문제인 것 같습니다. 

그리고 몰랐는데 이분탐색을 제공하는 함수가 있다는 것을 알았습니다.

 

풀이와 해당 내용을 정리합니다.

 

[Java]

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

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] A = new int[n];
        for (int i = 0; i < n; i++) {
            A[i] = sc.nextInt();
        }
        Arrays.sort(A);
        int m = sc.nextInt();
        for (int i = 0; i < m; i++) {
            int num = sc.nextInt();
            int left = 0;
            int right = A.length - 1;
            boolean flag = false;
            while (left <= right) {
                int midIndex = (left + right) / 2;
                int midValue = A[midIndex];
                if (midValue > num) {
                    right = midIndex - 1;
                } else if (midValue < num) {
                    left = midIndex + 1;
                } else { //찾음
                    flag = true;
                    System.out.println(1);
                    break;
                }
            }
            if (!flag) {
                System.out.println(0);
            }
        }
    }
}

 

 

 

[이분탐색 기록]

 

함수화

private static int binarySearch(int[] arr, int from, int to, int num) {
        int left = from;
        int right = to - 1;
        while (left <= right) {
            int midIndex = (left + right) / 2;
            int midValue = arr[midIndex];
            if (midValue > num) {
                right = midIndex - 1;
            } else if (midValue < num) {
                left = midIndex + 1;
            } else { //찾은 인덱스 반환
                return midIndex;
            }
        }
        return -1; //못칮음
    }

 

 

[이분탐색 내장함수]

정렬한다음에 사용해야하고 찾는게 성공시에는 해당인덱스를 못찾을시에는 음수를 반환한다고 합니다.

 

Arrays.binarySearch(arr, value); //배열과 찾을 값