이분 탐색(이진 탐색)

이분 탐색이란 유한 정렬 배열의 탐색 알고리즘이다.

제한 사항
1. 유한한 크기
2. 정렬(sort)

주로 정렬되어 있는 자료들의 집합에서 특정 자료를 찾고자 할 때 많이 사용되며 절반씩 나눠가면서 해당 값을 찾아 매우 빠른 탐색 알고리즘이다.

이진 탐색은 '퀵정렬'과 유사하게 '분할 후 정복(divide and conquer)'의 전략을 사용한다.

'분할 후 정복' 전략을 사용하는 알고리즘은 문제를 나누어 해결해 나가는 방법을 사용해 실행시간은 log의 성질을 갖는다.

시간 복잡도

유한 정렬 배열의 크기를 N라 하면,

배열 내에 탐색 값이 없는 최악의 경우,

N 1/2 1/2 * 1/2... 으로 범위 내 원소가 하나가 될 때까지 진행하므로

N*(1/2)K = 1 -> K = log2N 

으로 수식화 할 수 있고, 양 변에 2K를 곱하고 log2를 취하여 정리하면

O(log2N)

으로 시간 복잡도를 나타낼 수 있다.

Java Code

public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
 
        binarySearch(2, arr);
    }
 
    public static void binarySearch(int iKey, int arr[]) {
        int mid;
        int left = 0;
        int right = arr.length - 1;
 
        while (right >= left) {
            mid = (right + left) / 2;
 
            if (iKey == arr[mid]) {
                System.out.println(iKey + " is in the array with index value: " + mid);
                break;
            }
 
            if (iKey < arr[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
 
        }
    }
}

응용

1. 이분탐색_최소 인덱스

단순한 이분 탐색의 경우, 찾으려는 값이 여러개 있는 경우, 처음 찾은 목표값 인덱스를 그대로 리턴한다. 만약 여러 개 있는 값중 인덱스가 작은 것을 리턴하고자 한다면 목표값을 찾았을 때 바로 리턴하지 않고, right의 범위를 하나 줄여 더 왼쪽편에도 목표값이 있는 지 찾게한다.

public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
 
        binarySearch(2, arr);
    }
 
    public static void binarySearch(int iKey, int arr[]) {
        int mid;
        int left = 0;
        int right = arr.length - 1;
 
        while (right >= left) {
            mid = (right + left) / 2;
 
            if (iKey == arr[mid]) {
                System.out.println(iKey + " is in the array with index value: " + mid);
                right = mid - 1;
            }
 
            if (iKey < arr[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
 
        }
    }
}

2. 이분탐색_최대 인덱스

최대 인덱스는 목표값을 찾았을 때 left의 범위를 하나 줄여 더 오른쪽 편에도 목표값이 있는 지 찾게 한다.

public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
 
        binarySearch(2, arr);
    }
 
    public static void binarySearch(int iKey, int arr[]) {
        int mid;
        int left = 0;
        int right = arr.length - 1;
 
        while (right >= left) {
            mid = (right + left) / 2;
 
            if (iKey == arr[mid]) {
                System.out.println(iKey + " is in the array with index value: " + mid);
                left = mid + 1;
            }
 
            if (iKey < arr[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
 
        }
    }
}

썸네일 출처

Pixabay로부터 입수된 mohamed Hassan님의 이미지 입니다.