이분 탐색 알고리즘(Binary Search Algorithm)

이분 탐색 이란?

이분 탐색 알고리즘은 정렬된 배열에서 원하는 값을 찾는 알고리즘이다. 배열을 이분해서

(mid = (left + right) / 2) 중간 값을 찾고, 그 중간 값과 찾고자 하는 값의 크기를 비교하여 다음 탐색 범위를 결정한다.

 

이 알고리즘은 탐색할 데이터의 개수가 많을 때 일반적인 선형 탐색 알고리즘보다 빠른 속도로 원하는 데이터를 찾을 수

있다. 이 알고리즘은 탐색할 배열이 이미 정렬되어 있어야 하므로, 정렬되지 않은 데이터에서는 사용할 수 없다.

 

이분 탐색 알고리즘의 시간 복잡도는 O(log n)이다. 이는 배열을 이분할 때마다 탐색 범위가 절반으로 줄어들기 때문에 배열의 크기가 클 수록 더욱 효율적인 알고리즘이 될 수 있다.

 

이분 탐색 알고리즘을 구현한 예시이다.

public static int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    
    while (left <= right) {
        int mid = (left + right) / 2;
        
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1;
}

계속 값을 중간으로 나누어 원하는 결과값을 찾는 코드이다.