[Java]자바로 이분탐색 연습 -기본, lower bound, upper bound-

1. 기본문제1

 

n개의 숫자가 오름차순으로 정렬된 상태로 주어집니다. 이후 m개의 숫자가 추가적으로 주어졌을 때, 각각의 숫자가 처음 주어진 n개의 숫자 중 몇 번째로 나온 숫자인지를 구하는 프로그램을 작성해보세요.

 

 

2. 풀이

 

배운대로 기본에 충실하게 만들어보자

 

Main 클래스 내에서 public static int 함수로 binarysearch를 만들고,

 

mid 포인트는 start + (end - start)/2로 하고

 

삼분탐색하지 말고, 이분탐색으로 arr[mid] >= target인 경우와, arr[mid] < target인 경우 2가지로 나누자.

 

그 뒤의 응용은 알아서...

 

근데 이 문제에서 핵심은..

 

arr[mid] == target인 경우 그 위치를 출력하라고 했다

 

근데 arr[mid] >= target인 경우와 arr[mid] < target인 경우로 나눠버리면, loc는 arr[mid] == target인 경우가 아니라, arr[mid] >= target인 최소 위치를 찾아준다.

 

따라서 arr[loc]가 target과 다르다면, arr에 target인 수가 없다는 뜻이므로, 그러한 검사 조건 arr[loc] != target도 추가해주자

 

import java.util.Scanner;

public class Main {

    public static int binarySearch(int[] arr, int target, int start, int end){

        while(start < end){
            int mid = start + (end - start)/2;

            if(arr[mid] >= target){
                end = mid;
            }else {
                start = mid + 1;
            }
        }

        return end;
    }
    public static void main(String[] args) {
        // 여기에 코드를 작성해주세요.

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();

        int[] arr = new int[n];

        for(int i = 0; i < n; i++){
            arr[i] = sc.nextInt();
        }

        for(int j = 0; j < m; j++){

            int target = sc.nextInt();

            int loc = binarySearch(arr,target,0,n);

            if(loc == n || arr[loc] != target){
                System.out.println(-1);
            } else {
                System.out.println(loc+1);
            }
        }
    }
}

 

3. lower bound

 

내가 찾는 값 target이 배열에 여러개 있다면, 이진탐색을 수행했을 때, 어떤 위치가 나오게 될지 알 수가 없다.

 

이런 경우에 특히 내가 원하는 값 target 이상이 처음으로 나오는 위치에 관심있는데, 이를 lower bound라고 부른다

 

 

lower bound는 원하는 값 target 이상의 값이 최초로 나오는 위치이다.

 

바꿔말하면, target보다 크거나 같은 원소의 위치들 중 가장 작은 값을 찾아야 한다는 뜻이다.

 

arr[mid] >= target인 가장 작은 mid

 

지금까지 배운 구현 그대로 자바에 적용해보면...

 

public static int lowerBound(int[] arr, int target, int start, int end){
    
    while(start < end){
        
        int mid = start + (end - start)/2;
        
        //arr[mid] >= target이면, mid 이후는 조건을 만족하므로.. 
        //가장 작은 mid로 end를 옮겨준다.
        if(arr[mid] >= target){
            end = mid;
        
        //arr[mid] < target이면, mid 이전은 조건을 만족하지 않으므로,
        //mid+1 ~ end까지 다시 탐색해준다
        } else {
            start = mid + 1;
        }
    }
    return end;
 }

 

4. upper bound

 

원하는 값 target을 초과하는 값이 최초로 나오는 위치이다.

 

 

 

바꿔말하면, target보다 큰 값이 가장 먼저 나오는 위치를 찾는 것이다.

 

즉, arr[mid] > target을 만족하는, 가장 작은 mid를 찾는 것이다.

 

putlic static int upperBound(int[] arr, int target, int start, int end){
    
    while(start < end){
        
        int mid = start + (end - start)/2;
        
        //arr[mid] > target이면, mid 이후는 조건을 만족하므로
        //조건을 만족하는 가장 작은 위치 mid로 end를 옮겨주어
        //start ~ mid까지, 가장 작은 arr[mid] > target을 만족하는 mid를 찾으러 간다
        if(arr[mid] > target){
            
            end = mid;
        
        //arr[mid] <= target이면, mid 이전은 조건을 만족하지 않는다.
        //따라서, mid+1 ~ end까지를 탐색해준다.
        } else {
            
            start = mid + 1;
        }
    }
    
    return end - 1;
 }

 

 

5. custom bound

 

lower bound와 upper bound를 잘 응용해서, 원하는 위치를 구하는 함수를 적절하게 구현해볼 수 있을 것이다.

 

target보다 작거나 같은 숫자들이 있는 위치 중, 가장 큰 위치를 구하는 함수를 작성한다면?

 

바꿔말하면, arr[mid] <= target을 만족하는 가장 큰 mid를 찾아야 한다.

 

따라서, arr[mid] <= target이라면, mid 이전은 모두 target이하이므로,

 

mid보다 큰 위치 start = mid + 1부터 end 사이에 조건을 만족하는 위치가 존재하는지 탐색해봐야한다.

 

반면, arr[mid] > target이면... mid 이후는 모두 target보다 크거나 같으므로, end = mid로 옮겨서, start부터 mid까지를 재탐색한다.

 

public static customBound(int[] arr, int target, int start, int end){
    
    while (start < end){
        
        int mid = start + (end - start)/2;
        
        if(arr[mid] <= target){
            
            start = mid + 1;
        
        } else {
            
            end = mid;
        }
    
    }
    
    return end;
}

 

당연하지만, lower bound나 upper bound, custom bound 이런 것들은 예를 들어 end = n이거나 start = -1이 나오는등,

 

불가능한 경우가 나온다면 배열 내에 조건을 만족하는 값이 없다고 해석하면 된다

 

6. 연습문제

 

n개의 숫자가 오름차순으로 정렬된 상태로 주어집니다. 이후 m개의 숫자가 추가적으로 주어졌을 때, 각각의 숫자가 처음 주어진 n개의 숫자 중 몇 번 나왔는지를 구하는 프로그램을 작성해보세요.

 

upper bound를 end - 1로 return하는 식으로 구현한다면, lower bound가 upper bound보다 큰 경우에 해당하는 값이 배열에 존재하지 않는 것이다.

 

import java.util.Scanner;

public class Main {
    
    public static int lowerBound(int[] arr, int target, int start, int end){

        while (start < end){
            
            int mid = start + (end - start)/2;

            if(arr[mid] >= target){
                end = mid;
            } else {
                start = mid + 1;
            }
        }

        return end;
    }

    public static int upperBound(int[] arr, int target, int start, int end){

        while(start < end){

            int mid = start + (end - start)/2;

            if(arr[mid] > target){
                end = mid;
            } else {
                start = mid + 1;
            }
        }

        return end - 1;
    }
    public static void main(String[] args) {
        // 여기에 코드를 작성해주세요.

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();

        int[] arr = new int[n];

        for(int i = 0; i < n; i++){
            arr[i] = sc.nextInt();
        }

        for(int j = 0; j < m; j++){

            int target = sc.nextInt();

            int lower = lowerBound(arr,target,0,n);
            int upper = upperBound(arr,target,0,n);

            if(lower > upper){
                System.out.println(0);
            } else {
                System.out.println(upper-lower+1);
            }
        }
    }
}