이진 검색(Binary Search)

이진 검색(Binary Search)은 정렬된 배열에서 특정 값을 효율적으로 찾는 검색 알고리즘이다.

이진 검색의 작동 원리는 다음과 같다:

1. 먼저, 배열의 중간 인덱스에 위치한 값을 확인한다.
2. 이 값이 찾고자 하는 값과 동일한지 확인한다.
3. 만약 동일하다면, 검색을 종료하고 해당 인덱스를 반환한다.
4. 만약 찾고자 하는 값이 중간 값보다 크다면, 중간 인덱스를 기준으로 왼쪽 부분(작은 값들이 있는 부분)을 버리고 오른쪽 부분(큰 값들이 있는 부분)에서 검색을 계속한다.
5. 만약 찾고자 하는 값이 중간 값보다 작다면, 중간 인덱스를 기준으로 오른쪽 부분(큰 값들이 있는 부분)을 버리고 왼쪽 부분(작은 값들이 있는 부분)에서 검색을 계속한다.
6. 이렇게 반복하면서 검색 범위를 반으로 줄여가며 찾고자 하는 값을 찾는다.

이진 검색은 데이터가 정렬되어 있어야 사용할 수 있으며, 그 특성상 선형 검색보다 훨씬 빠르게 검색을 수행할 수 있다. 이진 검색의 시간 복잡도는 O(log n)이다. 이는 n개의 요소를 가진 리스트에서, 이진 검색이 한 번 실행될 때마다 검색해야 할 요소의 수가 절반으로 줄어들기 때문입니다. 이는 큰 데이터셋에서 매우 효율적이다.

class BinarySearch {
    // 이진 검색 메소드
    int binarySearch(int arr[], int x) {
        int l = 0, r = arr.length - 1;
        // 왼쪽 인덱스(l)가 오른쪽 인덱스(r)보다 작거나 같을 동안 반복
        while (l <= r) {
            // 중간 인덱스(m)를 계산
            int m = l + (r - l) / 2;
 
            // x가 배열의 중간 요소와 같은지 확인
            if (arr[m] == x)
                return m; // 같으면 x의 인덱스인 m 반환
 
            // x가 중간 요소보다 크면, 왼쪽 절반을 무시
            if (arr[m] < x)
                l = m + 1;
 
            // x가 중간 요소보다 작으면, 오른쪽 절반을 무시
            else
                r = m - 1;
        }
 
        // 위 반복문을 통과했는데도 리턴이 안되었다면, x는 배열에 없는 것
        return -1; // 그래서 -1 반환
    }
 
    public static void main(String args[]) {
        BinarySearch bs = new BinarySearch();
        int arr[] = {2, 3, 4, 10, 40}; // 검색 대상 배열
        int x = 10; // 찾고자 하는 값
        // binarySearch 메소드를 사용하여 x의 위치 검색
        int result = bs.binarySearch(arr, x);
        // x의 위치에 따라 결과 출력
        if (result == -1)
            System.out.println("배열에 원소가 없습니다."); // x가 배열에 없다면
        else
            System.out.println("원소가 " + result + "번째 인덱스에 있습니다."); // x가 배열에 있다면
    }
}

주어진 배열 **arr**에서 값 **x**를 찾는 binarySearch 메소드를 정의하고 있다. **x**가 배열에 있으면 해당 인덱스를, 없으면 **-1**을 반환한다.

binarySearch 메소드는 배열의 중앙에 있는 값이 **x**와 같은지 확인하고, **x**가 중앙값보다 크면 왼쪽 반을 무시하고, **x**가 중앙값보다 작으면 오른쪽 반을 무시하는 방식으로 동작한다. 이런 방식으로 검색 범위를 절반씩 줄여나가면서 **x**를 찾는다.