이분 탐색

이분 탐색

---

오름차순으로 정렬된 정수 리스트에서 원하는 데이터를 찾는 알고리즘으로 한 번 검색할 때마다 검색 범위를 반으로 줄여가며 검색한다.

찾고자 하는 값 : ans
검색 범위의 왼쪽 끝 : left
검색 범위의 오른쪽 끝 : right
검색 범위의 중간값 : mid

알고리즘의 작동 방식은 아래와 같다.

검색 범위가 없다면 검색 값 없음 리턴
mid == ans이면 mid 리턴
mid < ans이면 앞쪽 절반에서 다시 탐색
mid > ans이면 뒤쪽 절반에서 다시 탐색

보통은 성능 문제때문에 재귀적으로 구현하지 않고 반복문으로 구현한다.

---

이분 탐색 구현 코드

    // 재귀 형태로 구현한 이분 탐색 코드, 값이 없다면 -1 리턴
    int binarySearchRecursion(int[] arr, int left, int right, int value) {
        if (left > right) return -1;

        int mid = (left + right) / 2;

        if (arr[mid] == value) return mid;
        else if (arr[mid] < value) return binarySearchRecursion(arr, left, mid - 1, value);
        else return binarySearchRecursion(arr, mid + 1, right, value);
    }

    // 반복문 형태로 구현한 이분 탐색 코드, 값이 없다면 -1 리턴
    int binarySearchLoop(int[] arr, int left, int right, int value) {
        while (left <= right) {
            int mid = (left + right) / 2;

            if (arr[mid] == value) return mid;
            else if (arr[mid] < value) right = mid - 1;
            else left = mid + 1;
        }

        return -1;
    }

---

Lower Bound와 Upper Bound

이분 탐색은 정확하게 찾는 값이 없으면 값이 없다고 리턴한다. 하지만 특정 값을 정렬된 배열의 어느 위치에 넣어야 하는지와 같은 기능을 수행하기는 어렵다. 원하는 값을 찾지 못했어도 가장 근접한 값을 리턴해주는 것이 Lower Bound와 Upper Bound이다.

Lower Bound

찾고자 하는 값(value)보다 크거나 같은(이상) 첫 번째 위치 반환

Upper Bound

찾고자 하는 값(value)보다 큰(초과) 첫 번째 위치 반환

---

Lower Bound와 Upper Bound 구현 코드

    // Lower Bound 코드, 원하는 값 이상의 값이 나타나는 첫 인덱스 리턴
    int lowerBound(int[] arr, int left, int right, int value) {
        while (left < right) {
            int mid = (left + right) / 2;
            
            if (arr[mid] < value) left = mid + 1;
            else right = mid;
        }

        return left;
    }

    // Upper Bound 코드, 원하는 값 초과의 값이 나타나는 첫 인덱스 리턴

    int upperBound(int[] arr, int left, int right, int value) {
        while (left < right) {
            int mid = (left + right) / 2;

            if (arr[mid] <= value) left = mid + 1;
            else right = mid;
        }

        return left;
    }

코드를 보면 이분 탐색, Lower Bound, Upper Bound가 매우 흡사하다.
하지만 이분 탐색은 정확하게 내가 찾는 값이 있다면 그 인덱스를 리턴하고, Lower Bound와 Upper Bound는 탐색 범위가 없을 때까지 추가 탐색한다.

Lower Bound(찾는 값 이상)와 Upper Bound(찾는 값 초과)의 개념에 따라
Lower Bound는 내가 찾는 값보다 작을 때만 왼쪽 절반을 탐색하고,
Upper Bound는 내가 찾는 값보다 클 때만 오른쪽 절반을 탐색한다.
즉 arr[mid] = value일 때
Lower Bound = 오른쪽 절반 탐색
Upper Bound = 왼쪽 절반 탐색

※Lower Bound나 Upper Bound를 마치고 리턴하는 값은 left나 right나 동일하다. 취향따라 리턴하면 된다.