이진 탐색(binary search)

이진 탐색은 분할 정복의 기본이라고 할 수 있다. 개념은 알고 있었는데 직접 코드로 짜본 적이 있었나 싶어서 짚고 넘어간다.

원리

간단하게 말하면 "반으로 쪼개기"이다. head에서 tail까지 범위의 배열의 가운데 인덱스인 mid를 정해서 그 수와 찾고자 하는 수를 비교한다. 그래서 "찾는수 < 가운데 수" 이면 탐색 범위를 [head ~ mid]로 쪼개 탐색하고, 반대로 "찾는수 > 가운데 수"이면 탐색 범위를 [mid+1 ~ tail]로 쪼개서 탐색하는 것이다. 이 방식은 O(logn)의 시간 복잡도를 가져 선형 탐색보다 빠르다.

바로 구현에 들어가보자.

public class BinarySearch {
    public static String search(int[] arr, int head, int tail, int target) {
        while (head < tail) {
            int mid = (head + tail) / 2;
 
            if (target < arr[mid]) {
                tail = mid;
            } else if (target == arr[mid]) {
                return "탐색 성공";
            } else if (target > arr[mid]) {
                head = mid + 1;
            }
        }
        return "탐색 실패";
    }
 
    public static void main(String[] args) {
        int[] arr = { 5, 7, 15, 26, 45, 74, 133 };
        int head = 0;
        int tail = arr.length - 1;
 
        System.out.println(search(arr, head, tail, 26));
        System.out.println(search(arr, head, tail, 33));
 
    }
}
 

결과

탐색 성공
탐색 실패