[Algorithm] 이진 탐색 알고리즘 : 데이터 정렬과 검색 최적화 (Binary Search, Java)

 

자바를 활용하다 보면 데이터 집합에서 특정 값을 빠르게 찾아야 할 때가 있습니다.

 

예를 들어, 정렬된 배열이나 리스트에서 원하는 값을 효율적으로 검색해야 하는 경우가 그렇습니다. 이러한 상황에서 사용하는 것이 바로 이진 탐색(Binary Search)입니다.

 

이진 탐색(Binary Search)란❓

이진 탐색은 데이터가 정렬된 상태에서 중간 값을 기준으로 탐색 범위를 절반씩 좁혀가며 원하는 값을 찾는 효율적인 알고리즘입니다.

 

동작 방식

이진 탐색은 다음과 같은 단계로 동작합니다

1. 초기 설정: 탐색 범위의 시작점(left)과 끝점(right)을 설정합니다.
   • 처음에는 배열의 시작 인덱스와 끝 인덱스를 사용합니다.
2. 중간점 계산: 중간 인덱스(mid)를 계산합니다.
   • mid = left + (right - left) / 2
3. 값 비교:
   • 중간 인덱스의 값이 찾고자 하는 값(target)과 같다면 탐색을 종료합니다.
   • 중간 인덱스의 값이 찾고자 하는 값보다 크다면, ➡️ mid > target
     • 오른쪽 절반은 탐색할 필요가 없으므로 right = mid - 1로 설정하여 범위를 줄여줍니다.
   • 중간 인덱스의 값이 찾고자 하는 값보다 작다면, ➡️ mid < target
     • 왼쪽 절반은 탐색할 필요가 없으므로 left = mid + 1로 설정하여 범위를 줄여줍니다.
4. 반복: 값이 발견되거나 탐색 범위가 없어질 때까지 2번과 3번 단계를 반복합니다.

이진 탐색의 핵심은 탐색 범위를 절반으로 좁혀가며 원하는 값을 빠르게 찾는 것입니다.

 

이진 탐색(Binary Search) 예시

만약 위 그림을 처럼 배열이 있습니다. 이 배열에서 47이 존재하는지 찾는다면 다음과 같이 동작하게 됩니다.

 

1. 배열 초기 설정

• 주어진 배열(arr)
  • int [] arr = {0, 4, 7, 10, 14, 23, 45, 47, 53};
• 시작점(left)
  • 배열의 첫 번째 인덱스인 0
• 끝점(right)
  • 배열의 마지막 인덱스인 8

 

2. 중간 인덱스 계산(mid)

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

 

 

3. 값 비교

 

• 초기 상태
  • left = 0, right = 8
• 첫 번째 반복
  • mid = 0 + (8 - 0) / 2 = 4
  • arr [mid] = arr [4] = 14
  • 14는 47보다 작으므로,
    • 왼쪽 절반은 탐색할 필요가 없기 때문에 left를 mid + 1로 업데이트하여 검색 범위를 오른쪽 절반으로 좁힙니다.
• 두 번째 반복
  • left =  4 + 1 ➡️ 5(Update✅), right = 8 
  • mid = 5 + (8 - 5) / 2 = 6(Update✅)
  • arr [mid] = arr[6] = 45
  • 45는 47보다 작으므로,
    • 왼쪽 절반은 탐색할 필요가 없기 때문에 다시 left를 mid + 1로 업데이트하여 검색 범위를 오른쪽 절반으로 좁힙니다.
• 세 번째 반복:
  • left = 6+1 ➡️  7(Update✅), right = 8
  • mid = 7 + (8 - 7) / 2 = 7 (Update✅)
  • arr[mid] = arr [7] = 47
  • 47을 찾았으므로 검색을 종료하고 해당 위치를 출력합니다.

 

 

left + (right - left) / 2

left + (right - left) / 2; 외에도 중간값을 계산하는 다양한 방법이 있습니다.

 

하지만 중요한 것은, 이 공식을 사용하는 이유는 정수 오버플로를 방지하면서 중간값을 안전하게 계산할 수 있기 때문입니다.

 

다른 방법을 사용해서 중간값을 계산할 수 있지만, 오버플로를 방지하면서 중간값을 계산하는 공식은 매우 중요합니다.

 

 

• 연산 순서:
  • (right - left)는 right와 left의 차이를 나타내며, 이 값은 항상 음수가 아니라는 점에서 시작합니다.
  • right와 left는 모두 배열 인덱스를 나타내므로, right - left는 항상 음수가 아닌 양수입니다.
  • 따라서 (right - left) / 2는 항상 음수가 아니며, 0 이상의 값을 가집니다.
• 정수 연산:
  • Java에서 정수 연산은 항상 정수 값을 반환하며, 소수점 이하는 버려집니다.
  • (right - left) / 2는 항상 정수 값을 반환하므로 소수점 문제는 발생하지 않습니다.
• 범위:
  • left와 right는 배열의 인덱스를 나타내는 값이며, 배열의 크기가 Integer.MAX_VALUE보다 작기 때문에 (right - left)의 절댓값은 Integer.MAX_VALUE를 넘지 않습니다.
  • 따라서 left + (right - left) / 2는 Integer.MAX_VALUE를 초과하지 않고 계산됩니다.
• Overflow 방지:
  • (right - left) / 2는 자바에서는 양의 정수로 계산되며, 이는 left와 right가 Integer.MAX_VALUE를 넘지 않는 한 오버플로우 문제가 발생하지 않습니다.

 

 

이진 탐색(Binary Search) 예제

public class BinarySearchExample {
    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; // target found
            }
            if (arr[mid] < target) {
                left = mid + 1; // search in the right half
            } else {
                right = mid - 1; // search in the left half
            }
        }

        return -1; // target not found
    }

    public static void main(String[] args) {
        int[] sortedArray = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
        int target = 7;

        int result = binarySearch(sortedArray, target);
        if (result == -1) {
            System.out.println("Target not found in the array.");
        } else {
            System.out.println("Target found at index: " + result);
        }
    }
}

 

실행 결과

Target found at index: 3

 

 

이진 탐색(Binary Search)의 장단점

장점

1. 빠른 검색 속도
   • 이진 탐색은 시간 복잡도가 O(log n)으로, 데이터 양이 많아질수록 선형 탐색(O(n))보다 훨씬 빠릅니다.
2. 간단한 구현
   •  구현이 비교적 간단하여 코드 작성이 용이합니다.

단점

1. 정렬된 데이터 필요
   •  이진 탐색을 사용하기 위해서는 데이터가 정렬되어 있어야 합니다. 데이터 정렬에 추가적인 비용이 발생할 수 있습니다.
2. 동적 데이터 처리 어려움
   •  데이터의 삽입, 삭제가 빈번하게 일어나는 경우, 매번 정렬을 유지해야 하기 때문에 비효율적일 수 있습니다.