이분 탐색(Binary Search)

1. 이분 탐색(Binary Search)이란?

- 정렬된 배열에서 원하는 값을 빠르게 찾기 위해 사용하는 기본적인 알고리즘이다.

- 정렬된 배열의 중앙값과 비교하면서 찾고자 하는 값이 중앙값보다 작으면 왼쪽 부분 배열, 크면 오른쪽 부분 배열로 범위를 좁혀나간다.

- 탐색 범위를 매번 절반으로 줄이므로 O(logN)의 시간복잡도를 가진다.

- 정렬이 필수적으로 되어있어야 한다.

- 최적의 해, 임계값 알고리즘에 활용된다.

 

2. 이분 탐색 구현

- left와 right, mid 변수로 시작과 끝, 중앙 인덱스를 설정하고 값과 비교하며 범위를 축소한다. 

public class BinarySearch {
    // 정렬된 배열에서 target 값을 탐색하여 인덱스를 반환 (찾지 못하면 -1 반환)
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length-1;

        while(left <= right) {
            // 중앙 인덱스 계산(left와 right의 평균)
            int mid = left+(right-left)/2;

            // 중앙값과 target 비교
            if(arr[mid] == target) {
                return mid;
            } else if(arr[mid] < target) {
                // target은 오른쪽 부분 배열에 존재
                left = mid+1;
            } else {
                // target은 왼쪽 부분 배열에 존재
                right = mid-1;
            }
        }
        // target이 존재하지 않을 때
        return -1;
    }

    public static void main(String[] args) {
        // 예제 데이터
        int[] arr = {1, 3, 5, 7, 9, 11};
        int target = 7;

        int index = binarySearch(arr, target);

        // 출력: 3
        System.out.println(index);
    }
}