이분 탐색(Binary Search - Lower Bound, Upper Bound)

Binary Search

이분 탐색은 데이터가 정렬되어 있는 배열에서 특정한 원소를 찾는 알고리즘이다. 이분 탐색을 사용하기 위해서는 원소가 오름차순 또한 내림차순으로 정렬되어 있어야 한다.

이분 탐색 과정은 다음과 같다(오름차순 정렬이 되어있는 상태).

1. 찾는 원소를 targetm, 찾고자 하는 범위의 양 끝 인덱스를 lo, hi라고 할 때, lo와 hi의 중간 값 mid를 구한다.
2. arr[mid]를 찾고자 하는 원소와 비교한다.
   • arr[mid]이 target와 같은 경우 : 탐색을 종료한다.
   • arr[mid]가 target보다 큰 경우 : target의 위치는 mid 보다 작으므로 hi 를 mid - 1로 갱신한 뒤 2번 과정을 반복한다.
   • arr[mid]가 target보다 작은 경우 : target의 위치는 mid 보다 크므로 lo 를 mid + 1로 갱신한 뒤 2번 과정을 반복한다.

Code

public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {2, 3 ,5, 8, 11, 26};

		// 출력 값은 3
        System.out.println(binarySearch(arr, 8));
    }

    public static int binarySearch(int[] arr, int target){
        int lo = 0;
        int hi = arr.length - 1;

        while(lo <= hi){
            int mid = (lo + hi) / 2;

            if(arr[mid] == target){
                return mid;
            }
            else if(arr[mid] > target){
                hi = mid - 1;
            }
            else{
                lo = mid + 1;
            }
        }
        return -1;
    }

}

Lower Bound

Lower Bound는 찾고자 하는 target값 보다 크거나 같은 첫번째 위치(이상)를 반환한다.
Lower Bound에서는 target값 보다 이상인 범위를 찾으므로, 크거나 같은 경우 hi값을 mid - 1이 아닌 mid로 갱신한다.

Code

public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {2, 3 ,5, 8, 11, 26};

		// 출력 값은 3
        System.out.println(lowerBound(arr, 8));
    }

    public static int lowerBound(int[] arr, int target){
        int lo = 0;
        int hi = arr.length - 1;

        while(lo < hi){
            int mid = (lo + hi) / 2;

            if(arr[mid] >= target){
                hi = mid;
            }
            else{
                lo = mid + 1;
            }
        }
        return hi;
    }

}

Upper Bound

Upper Bound는 찾고자 하는 target값 보다 큰 첫번째 위치(초과)를 반환한다.
Upper Bound는 초과인 값이므로, Lower Bound의 경우에서 같은 값인 조건을 빼면 된다.

Code

public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {2, 3 ,5, 8, 11, 26};

		// 출력값 은 4
        System.out.println(upperBound(arr, 8));
    }

    public static int upperBound(int[] arr, int target){
        int lo = 0;
        int hi = arr.length - 1;

        while(lo < hi){
            int mid = (lo + hi) / 2;

            if(arr[mid] > target){
                hi = mid;
            }
            else{
                lo = mid + 1;
            }
        }
        return hi;
    }
}