이분 탐색 코드로 구현하기 - 자바

이분 탐색을 통해 특정 숫자를 찾을 때는 일반적인 이분 탐색을 구현하여 풀이하면 된다. 그러나 만약 특정 수의 개수를 카운팅 하고 싶은 상황에서는 어떻게 해야 할까?

아래와 같이 일반적으로 구현하게 된다면 찾고자 하는 숫자의 index를 찾을 수는 있겠지만 몇 개가 존재하는지 세는 것은 추가적인 연산이 필요할 것이다.

일반적인 이분 탐색 구현

private static boolean find(int num, int[] arr) {

            int l = 0;
            int r = arr.length-1;

            while(l <= r){
                int mid = (l+r) / 2;

                if(arr[mid] == num){
                    return true;
                } else if(arr[mid] > num){
                    r = mid-1;
                } else {
                    l = mid+1;
                }
            }

            return false;

        }

 

그래서 아래와 같은 코드로 왼쪽과 오른쪽을 스캔하는 코드를 구현해보았다. 찾은 index를 기준으로 왼쪽과 오른쪽으로 각각 탐색하면서 카운트를 세는 것이다. 그런데 아래와 같은 방법으로 하게 되면 특정 케이스에 한해서는 binary search의 log n을 보장할 순 없을 것이다.

 

private static void binarySearch(int num) {
        int cnt = 0;
        int l = 0;
        int r = arr.length-1;

        while(l<=r){
            int mid = (l+r) / 2;
            if(arr[mid] == num){
                int temp = mid-1;
                while(mid < arr.length && arr[mid] == num){
                    cnt++;
                    mid++;
                }
                while(temp >= 0 && arr[temp] == num){
                    cnt++;
                    temp--;
                }
                break;
            } else if(arr[mid] > num){
                r = mid -1;
            } else {
                l = mid + 1;
            }

        }
        sb.append(cnt).append(" ");
    }

 

그래서 처음부터 왼쪽 오른쪽을 나눠서 찾는 lower bound와 upper bound라는 개념을 통해 구현하게 되면 위의 코드보다 빠르게 동작하게 된다. lower bound는 찾고자 하는 특정 숫자와 같거나 큰 값이 처음 나오는 위치를 반환해준다. 그리고 upper bound는 특정 숫자보다 처음으로 큰 값이 나오는 위치를 반환해준다.

 

Lower Bound , Upper Bound 구현

    private static int lowerBound(int num){
        int l = 0;
        int r = arr.length;

        while(l<r){
            int mid = (l+r)/2;

            if(arr[mid] >= num){
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }

    private static int upperBound(int num){
        int l = 0;
        int r = arr.length;

        while(l<r){
            int mid = (l+r)/2;
            if(arr[mid] <= num){
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return l;
    }

 

이번에는 이분 탐색으로 특정 조건을 만족하는 수를 찾는 상황에서 가장 큰 수를 찾을 때의 이분 탐색을 구현해보았다. 그리고 이번 문제를 풀면서 이분 탐색에서 left 설정을 조심해야 하는 것을 깨달았는데, 만약 left가 0으로 시작하게 설정한다면 런타임 에러인 java.lang.ArithmeticException: / by zero가 나올 수 있으니 꼭 시작 조건을 1로 설정하자

private static void binarySearch(int[] arr, int n, int k) {

        long left = 1;
        long right = arr[arr.length-1];
        long ans = 0;

        while(left<=right){

            long mid = (left + right)/2;
            long res = 0;

            for(int i=0; i<arr.length; i++){
                res += arr[i]/mid;
            }

            if(res >= n){
                ans = Math.max(mid, ans);
                left = mid + 1;
            } else {
                right = mid - 1;
            }

        }

        System.out.println(ans);

    }

 

출처 : jackpot53.tistory.com/33

이진탐색-상/하한선((lower bound,upper bound)