2. 알고리즘 이진 탐색

이진 탐색(Binary Search)은 정렬된 배열에서 특정한 값을 찾는 알고리즘입니다. 이진 탐색은 배열의 중간 값과 찾고자 하는 값을 비교하면서 범위를 좁혀가는 방식으로 동작합니다. 배열이 정렬되어 있어야만 이진 탐색을 사용할 수 있습니다.

이진 탐색의 동작원리

1. 탐색할 배열의 중간 인덱스를 계산합니다.

2. 중간 인덱스의 값과 찾고자 하는 값을 비교합니다.

   • 만약 중간 값이 찾고자 하는 값과 같다면 탐색을 종료합니다.

   • 만약 중간 값이 찾고자 하는 값보다 작다면, 배열의 오른쪽 절반을 대상으로 이진 탐색을 수행합니다.

   • 만약 중간 값이 찾고자 하는 값보다 크다면, 배열의 왼쪽 절반을 대상으로 이진 탐색을 수행합니다.

3. 탐색 범위가 좁아질 때까지 위의 과정을 반복합니다.

이진 탐색을 Java로 구현한 예시를 살펴보겠습니다

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; // 오른쪽 절반을 탐색하기 위해 left 값을 갱신
        } else {
            right = mid - 1; // 왼쪽 절반을 탐색하기 위해 right 값을 갱신
        }
    }

    return -1; // 찾고자 하는 값이 배열에 없음
}

위의 예시에서는 이진 탐색을 수행하는 binarySearch 메서드를 정의하였습니다. 주어진 배열 arr에서 target 값을 탐색하여 해당 인덱스를 반환합니다. 탐색 범위를 좁혀가는 과정은 left와 right 변수를 사용하여 구현됩니다. 반복문을 통해 탐색 범위가 좁아질 때까지 이진 탐색을 반복합니다.

이진 탐색은 탐색 범위를 반으로 나누는 방식으로 동작하기 때문에 평균적으로 O(log n)의 시간 복잡도를 가지며, 매우 효율적인 탐색 알고리즘입니다. 그러나 이진 탐색을 사용하기 위해서는 배열이 정렬되어 있어야 한다는 점에 유의해야 합니다.