[알고리즘] 이진 탐색 (이분탐색)

이진탐색이란?

---

정렬되어 있는 데이터에서 원하는 값을 찾아내는 알고리즘. 주어진 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는 방법.

* 특징

• 시간 복잡도: O(logN)
• 중앙값 비교를 통한 대상 축소 방식
• 정렬 데이터에서 원하는 데이터를 탐색하는 일반적인 알고리즘
• 대규모 데이터를 다루는 경우에 유용

핵심 이론

---

오름차순으로 정렬된 데이터에서 다음 4가지 과정을 반복한다.

1. 현재 데이터셋의 중앙값(median)을 선택한다.
2. 중앙값 > 타깃 데이터(taget data)일 때 중앙값 기준으로 왼쪽 데이터셋을 선택한다.
3. 중앙값 < 타깃 데이터일 때 주앙값 기준으로 오른쪽 데이터셋을 선택한다.
4. 과정 1~3을 반복하다가 중앙값 == 타깃 데이터일 때 탐색을 종료한다.

예시)

• 다음과 같은 정렬된 배열이 있다고 가정해보자.
• 우리가 찾는 값이 11이라고 가정해보자.

1 3 5 7 9 11 13 15 17 19

1. 중간 인덱스(left + right) / 2를 선택합니다. -> 중간 인덱스는 (0 + 9) / 2 = 4
2. 중간 값인 9와 찾고자 하는 값인 11이 일치하지 않으므로 탐색 범위를 다시 좁힌다.
3. 찾고자 하는 값이 중간값보다 크므로, 중간값의 오른쪽 부분 배열에서 탐색을 시작한다. -> 중간 인덱스 + 1부터 right까지(인덱스 5 ~ 9) 탐색.
4. 중간 인덱스를 다시 선택 -> (5 + 9) / 2 = 7
5. 위 과정을 반복하여서 11을 찾는다.

알고리즘 구현 방식

---

1. 재귀

// 매개변수로 배열 arr, 찾고자 하는 값 target, 배열의 왼쪽 끝을 가리키는 left, 배열의 오른쪽 끝을 가리키는 right를 전달받는다.

public static int binarySearchRecursive(int[] arr, int target, int left, int right) {
    if (left > right) {
        return -1;
    }
    // 현재 검색 범위의 중간값을 구하고, 이 값이 찾고자 하는 값인지 확인
    int mid = (left + right) / 2;
    
    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] > target) { // 만약 찾고자 하는 값이 중간값보다 작다면, 중간값의 왼쪽 부분 배열에서 재귀적으로 탐색
        return binarySearchRecursive(arr, target, left, mid - 1);
    } else { // 찾고자 하는 값이 중간값보다 크다면, 중간값의 오른쪽 부분 배열에서 재귀적으로 탐색
        return binarySearchRecursive(arr, target, mid + 1, right);
    }
}

• 재귀 함수를 사용한 방법은 코드가 간결하지만, 재귀 호출로 인해 스택 메모리를 많이 사용할 수 있다. 반면에 while문을 사용한 방법은 스택 메모리를 덜 사용하며, 구현이 복잡하지 않다.

2. while문

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) { // 찾고자 하는 값이 중간값보다 작다면, 중간값의 왼쪽 부분 배열에서 탐색을 수행해야 하므로 right 포인터를 중간값의 왼쪽으로 이동
            right = mid - 1;
        } else { // 고자 하는 값이 중간값보다 크다면, 중간값의 오른쪽 부분 배열에서 탐색을 수행해야 하므로 left 포인터를 중간값의 오른쪽으로 이동
            left = mid + 1;
        }
    }

    return -1;
}

레퍼런스

• 알고리즘 코딩테스트 자바편 - 김종관 지음