이진 탐색 (Binary Search)

탐색 과정

이진 탐색으로 7을 찾는 과정

이진 탐색(Binary Search) 알고리즘은 리스트에서 특정한 값의 위치를 찾는 알고리즘이다.

먼저 이 알고리즘은 반드시 정렬을 한 후에 탐색을 시작해야 한다.

 

탐색할 범위의 시작과 끝이 같은 경우에는 찾지 못한 것으로 본다.

 

그렇지 않은 경우에는 탐색할 범위의 중간값을 확인하여 찾고자 하는 값보다 크거나 작은지 확인한다.

만약 값이 같다면 검색에 성공하여 위치를 반환하고 탐색을 종료한다.

 

중앙값이 찾는 값보다 크면 새로운 최댓값으로, 작다면 새로운 최솟값으로 설정하여 다시 탐색을 시작한다.

 

반드시 정렬을 해야한다는 단점이 있지만, 검색을 반복할 때마다 탐색할 범위가
1/2로 줄어들기 때문에 탐색 속도가 빠른 편이다.

 

구현 코드

import java.util.Scanner;
public class Main{
    public static int[] numbers;

    public static boolean binarySearch(int start, int end, int target) {
        if (start > end) return false;
        if (start == end) return numbers[start] == target;

        int mid = (end + start) / 2; // 중간값 위치

        if (numbers[mid] == target) return true;
        
        // 중간 값이 작다면 새로운 최솟값으로 설정
        if (numbers[mid] < target) return binarySearch(mid + 1, end, target);
        
        // 중간 값이 크다면 새로운 최댓값으로 설정
        if (numbers[mid] >= target) return binarySearch(start, mid, target);

        return false;
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String[] buf;

        buf = scan.nextLine().split(" ");
        int numberCnt = Integer.parseInt(buf[0]);
        int questionCnt = Integer.parseInt(buf[1]);

        buf = scan.nextLine().split(" ");
        numbers = new int[numberCnt];
        for (int i = 0; i < numberCnt; i++) {
            numbers[i] = Integer.parseInt(buf[i]);
        }

        buf = scan.nextLine().split(" ");
        for (int i = 0; i < questionCnt; i++) {
            if (binarySearch(0, numberCnt - 1, Integer.parseInt(buf[i]))) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
    }
}

 

참고 문서

이진 검색 알고리즘 - 위키백과, 우리 모두의 백과사전 - https://ko.wikipedia.org/wiki/이진_검색_알고리즘