이분 탐색(Binary Search) 개념과 구현

이분 탐색

• 순차적 탐색보다 빠른 방식(시간 복잡도 낮음)
• 정렬된 배열에서 특정 원소를 찾을 때 중간 값을 구함
• 중간 값이 찾는 원소가 아니라면 중간 값이 특정 원소보다 큰지 작은지 판단하여 탐색 범위를 수정
• 이러한 방식으로 탐색 범위를 반씩 줄여 특정 원소를 찾는 방법이 이분 탐색

 

 

이분 탐색의 기본 원리

1. 배열의 중앙 요소를 선택한다.
2. 찾고자 하는 값이 중앙 요소보다 작으면 왼쪽 절반을 탐색하고 크면 오른쪽 절반을 탐색한다.
3. 이 과정을 반복하여 값을 찾거나 배열이 비어있을 때까지 진행한다.

 

 

이분 탐색 구현

 

1) 반복적 방법(Iterative Approach)

public class BinarySearch {
    // 배열이 정렬되어 있다고 가정
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

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

            if (arr[mid] == target) {
                return mid; // 값을 찾았을 때의 인덱스 반환
            }
            if (arr[mid] < target) {
                left = mid + 1; // 오른쪽 절반 탐색
            } else {
                right = mid - 1; // 왼쪽 절반 탐색
            }
        }

        return -1; // 값을 찾지 못했을 때
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        int target = 5;
        int result = binarySearch(arr, target);

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

 

반복적 방법은 while 루프를 사용하여 이분 탐색을 수행한다.

이 방법은 스택 오버플로우 문제를 피할 수 있어 대규모 데이터에 적합하다.

 

중앙값 계산: (left + right) / 2 대신 left + (right - left) / 2를 사용해야 오버플로우를 방지할 수 있다. 매우 큰 정수 계산 시 전자를 사용하면 오버플로우가 발생할 수 있다.

 

동작 원리

초기화: 배열의 시작 인덱스 (left)와 끝 인덱스 (right)를 설정한다.

 

루프

• 중앙 인덱스 (mid)를 계산한다.
• 중앙 인덱스의 값이 목표값과 같으면 mid를 반환한다.
• 목표값이 중앙값보다 작으면 오른쪽 절반을 버리고 왼쪽 절반으로 탐색을 계속한다.
• 목표값이 중앙값보다 크면 왼쪽 절반을 버리고 오른쪽 절반으로 탐색을 계속한다.

 

종료: 목표값을 찾으면 해당 인덱스를 반환하고 찾지 못하면 -1을 반환한다.

 

 

 

2) 재귀적 방법 (Recursive Approach)

public class BinarySearch {
    // 배열이 정렬되어 있다고 가정
    public static int binarySearch(int[] arr, int left, int right, int target) {
        if (left <= right) {
            int mid = left + (right - left) / 2;

            if (arr[mid] == target) {
                return mid; // 값을 찾았을 때의 인덱스 반환
            }
            if (arr[mid] < target) {
                return binarySearch(arr, mid + 1, right, target); // 오른쪽 절반 탐색
            } else {
                return binarySearch(arr, left, mid - 1, target); // 왼쪽 절반 탐색
            }
        }

        return -1; // 값을 찾지 못했을 때
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        int target = 5;
        int result = binarySearch(arr, 0, arr.length - 1, target);

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

 

재귀적 방법은 함수가 자기 자신을 호출하여 이분 탐색을 수행한다.

구현이 간결하지만 깊은 재귀 호출이 필요한 경우 스택 오버플로우를 일으킬 수 있다.

 

동작 원리

배열의 시작 인덱스가 끝 인덱스보다 크면 탐색 범위가 없으므로 -1을 반환한다.

 

 

재귀 호출

• 중앙 인덱스 (mid)를 계산한다.
• 중앙 인덱스의 값이 목표값과 같으면 mid를 반환한다.
• 목표값이 중앙값보다 작으면 오른쪽 절반을 버리고 왼쪽 절반을 재귀적으로 탐색한다.
• 목표값이 중앙값보다 크면 왼쪽 절반을 버리고 오른쪽 절반을 재귀적으로 탐색한다.