24.12.26 TIL 이분 탐색

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

이분 탐색은 정렬된 배열에서 특정 값을 빠르게 찾기 위한 알고리즘입니다.
배열의 중간 값을 기준으로 탐색 범위를 절반으로 줄여나가는 방식으로 동작합니다.

2. 이분 탐색의 특징

1. 입력 데이터는 반드시 정렬되어 있어야 한다.
2. 탐색 범위가 점점 줄어들기 때문에 효율적이다.
3. 시간복잡도는 ( O(\log n) )으로, 매우 빠른 탐색 속도를 자랑한다.

3. 이분 탐색의 동작 원리

1. 배열의 중간 값을 확인한다.
2. 찾는 값이 중간 값보다 작으면, 왼쪽 절반만 탐색한다.
3. 찾는 값이 중간 값보다 크면, 오른쪽 절반만 탐색한다.
4. 이 과정을 값이 발견되거나, 탐색 범위가 없어질 때까지 반복한다.

4. 이분 탐색의 구현

1) 반복문 방식

public 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; // 값 찾음
        } else if (arr[mid] < target) {
            left = mid + 1; // 오른쪽으로 이동
        } else {
            right = mid - 1; // 왼쪽으로 이동
        }
    }

    return -1; // 값이 없음
}

2) 재귀 방식

public int binarySearchRecursive(int[] arr, int target, int left, int right) {
    if (left > right) return -1; // 종료 조건

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

    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] < target) {
        return binarySearchRecursive(arr, target, mid + 1, right);
    } else {
        return binarySearchRecursive(arr, target, left, mid - 1);
    }
}

5. 시간복잡도

• 최선의 경우: ( O(1) )
  • 중간 값이 바로 찾는 값일 때.
• 평균/최악의 경우: ( O(\log n) )
  • 매번 탐색 범위가 절반으로 줄어들기 때문.

6. 이분 탐색의 활용 사례

1. 정렬된 배열에서 값 찾기
   • 예: 특정 값 검색, 사전 조회.
2. Lower Bound / Upper Bound
   • Lower Bound: 특정 값 이상이 처음 나타나는 위치.
   • Upper Bound: 특정 값보다 큰 값이 처음 나타나는 위치.
3. 문제 해결
   • 예: 이진 검색 트리, 매개변수 탐색 문제 등.

7. 예제

문제: 정렬된 배열에서 특정 값을 찾는 프로그램

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

    int index = binarySearch(arr, target);
    if (index != -1) {
        System.out.println("Target found at index: " + index);
    } else {
        System.out.println("Target not found.");
    }
}

출력: Target found at index: 3

8. 느낀 점

이분 탐색은 효율적이고 직관적인 알고리즘으로, 문제 해결의 기본이 되는 중요한 기법이라고 느꼈습니다. 특히, 탐색 범위를 절반씩 줄여나가는 과정은 논리적이고 간결하며, 코드 구현에서도 큰 만족감을 주는 부분이었습니다. 앞으로 다양한 문제에서 이분 탐색을 적극 활용해보고 싶습니다.