초보 자바 프로그래밍(27) - 이진검색 (Binary Search)

이진 검색 대표 이미지

🔖 INDEX

 

 

이진 검색 (Binary Search)은 정렬된 배열에서 효율적으로 값을 찾는 알고리즘입니다. 이진 검색은 배열의 중간 요소를 확인하여 찾고자 하는 값이 중간 요소보다 큰지 작은지를 판단합니다. 찾고자 하는 값이 중간 요소보다 작으면 중간 요소 왼쪽의 절반을 검색하고, 찾고자 하는 값이 중간 요소보다 크면 중간 요소 오른쪽의 절반을 검색합니다. 이 과정을 반복하면서 원하는 값을 찾습니다.

 

이진 검색의 작동 방식

이진 검색의 작동 방식은 다음과 같습니다:

1. 배열의 가운데 요소를 확인합니다.
2. 가운데 요소가 원하는 값과 일치하면 해당 요소의 인덱스를 반환합니다.
3. 가운데 요소가 원하는 값보다 크면, 배열의 왼쪽 절반(가운데 요소보다 작은 값들)에서 검색을 계속합니다.
4. 가운데 요소가 원하는 값보다 작으면, 배열의 오른쪽 절반(가운데 요소보다 큰 값들)에서 검색을 계속합니다.
5. 원하는 값을 찾을 때까지 1~4단계를 반복합니다.
6. 검색 범위가 더 이상 없을 때까지 원하는 값을 찾지 못한 경우, 값이 배열에 없다고 판단하여 -1 또는 적절한 오류 코드를 반환합니다.

 

이진 검색의 특징

이진 검색의 장점은 다음과 같습니다:

• 효율적인 검색 시간: 이진 검색의 시간 복잡도는 O(log n)입니다. 여기서 n은 배열의 길이입니다. 이진 검색은 정렬된 배열에서 빠르게 값을 찾을 수 있기 때문에 대규모 데이터 세트에서도 효율적입니다.
• 적은 비교 횟수: 이진 검색은 배열을 반으로 나누어 탐색하기 때문에, 선형 검색에 비해 적은 비교 횟수로 원하는 값을 찾을 수 있습니다. ​

 

 

이진 검색 사용 시 다음과 같은 내용을 주의해야 합니다:

• 정렬된 배열에서만 사용 가능: 이진 검색은 정렬된 배열에서만 사용할 수 있습니다. 정렬되지 않은 배열에서 이진 검색을 사용하려면 먼저 데이터를 정렬해야 합니다. 정렬에 소요되는 시간이 추가적으로 필요하므로, 검색 전에 정렬을 수행해야 하는 경우 이진 검색의 효율성이 상대적으로 감소할 수 있습니다.
• 임의 접근이 가능한 데이터 구조에서만 사용 가능: 이진 검색은 배열과 같이 임의 접근이 가능한 데이터 구조에서만 사용할 수 있습니다. 연결 리스트와 같은 순차 접근 데이터 구조에서는 이진 검색을 사용하려면 추가적인 작업이 필요하거나 비효율적일 수 있습니다.
• 데이터의 중복성 처리: 이진 검색은 중복된 값을 가진 배열에서 특정 값의 첫 번째 또는 마지막 인덱스를 찾는 데 추가적인 처리가 필요합니다. 선형 검색은 처음부터 끝까지 배열을 검색하므로 중복된 값의 첫 번째 인덱스를 찾는 데 더 적합할 수 있습니다.

 

이진 검색의 구현 예제

자바에서 이진 검색 알고리즘을 구현하는 예제 코드는 다음과 같습니다:

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;
}

 

 

위의 이진 검색 알고리즘은 반복적인 방식으로 구현되어 있습니다. 이진 검색은 재귀적인 방식으로도 구현할 수 있습니다. 다음은 자바에서 재귀적 이진 검색 알고리즘을 구현한 예제 코드입니다:

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);
    }
}