[알고리즘/JAVA] 이진 탐색 : 개념 (수 찾기, 랜선 자르기) - Upper/Lower Bound

 

이진 탐색 (Binary Search)

정렬된 배열 또는 리스트를 반으로 나누어 가면서 원하는 값을 찾는 알고리즘이다. 배열이나 리스트가 정렬되어 있어야만 사용할 수 있다.

이진 탐색은 시간 복잡도가 O(log n)으로 매우 빠르다. 따라서 큰 데이터 집합에서도 빠르게 원하는 값을 찾을 수 있다

 

 

 

이진 탐색의 과정

https://en.wikipedia.org/wiki/Binary_search_algorithm

1. 탐색 범위 설정: 탐색 범위를 설정한다. 일반적으로는 전체 배열이나 리스트의 처음과 끝을 사용한다.
2. 중간 값 찾기: 설정된 범위에서 중간에 위치한 값을 찾는다.
3. 중간 값과 비교: 중간 값과 Key(찾고자 하는 값)의 크기를 비교한다.
4. 탐색 범위 업데이트: 중간 값과 Key의 크기에 따라 탐색 범위를 업데이트한다.
   1. 중간 값이 Key값보다 작을 경우 : 중간 값의 오른쪽 부분을 탐색 범위로 재설정한다.
   2. 중간 값이 Key값보다 클 경우 :  중간 값의 왼쪽 부분을 탐색 범위로 재설정한다.
5. 반복: 위의 과정을 반복하여 Key를 찾을 때까지 진행한다.

 

---

문제 : 수 찾기 (백준 1920)

 

 

가장 기본적인 이진 탐색 문제이다. 매우 심플하게 주어진 배열에서 Key를 탐색하는 문제이다.

 

 

 

이진 탐색 구현

public class Main {
    static int find(int[] array, int number){
        int start = 0;
        int end = array.length - 1;
        while(start <= end){
            int mid = (end + start) / 2;
            if(number == array[mid]){
                return 1;
            }
            else if(number > array[mid]){
                start = mid + 1;
            }
            else{
                end = mid - 1;
            }
        }
        return 0;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int[] array = new int[n];

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++){
            array[i] = Integer.parseInt(st.nextToken());
        }
        
        Arrays.sort(array); // 정렬

        st = new StringTokenizer(br.readLine());
        int m = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < m; i++){
            int number = Integer.parseInt(st.nextToken());
            System.out.println(find(array, number));
        }

    }
}

 

1. 이진 탐색은 정렬된 데이터에 대해서 사용할 수 있으므로 우선 데이터를 정렬한다.

2. 이진 탐색의 범위를 left ~ right로 설정한다.

3. left와 right의 중간점인 mid를 계산한다.

4. array[mid]와 key를 비교한다. key와 일치하는 인덱스를 찾을 때 까지 반복한다.

• array[mid] > key : 중간값이 key보다 큰 경우, mid를 기준으로 왼쪽으로 범위를 좁혀서 탐색한다. (end = mid - 1)
• array[mid] < key : 중간값이 key보다 작은 경우, mid를 기준으로 오른쪽으로 범위를 좁혀서 탐색한다. (start = mid + 1)
• array[mid] == key : 중간값이 key와 일치하는 경우, 탐색에 성공한 경우이므로 1를 반환한다.

 

 

 

Arrays.binarySearch() 사용

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int[] array = new int[n];

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++){
            array[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(array); // 정렬

        st = new StringTokenizer(br.readLine());
        int m = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < m; i++){
            int number = Integer.parseInt(st.nextToken());
            int index = Arrays.binarySearch(array, number);
            int result = index < 0 ? 0 : 1;
            System.out.println(result);
        }

    }
}

 

Java에서 이진 탐색 라이브러리를 제공한다. binarySearch() 메서드는 탐색 성공 시 인덱스의 위치를, 탐색 실패 시 음수를 반환한다.

 

 

---

이진 탐색 : 최소값과 최대값 찾기

 

Index	0	1	2	3	4	5	6	7
Key	10	20	20	20	20	30	30	40

 

만약 배열의 인덱스 0부터 7까지의 Key가 다음과 같다고 가정해보자. Key가 20인 인덱스의 최대값과 최소값을 찾아내야 한다면 어떻게 찾아야 할까? 이 때 사용되는 개념이 Lower Bound와 Upper Bound이다.

 

1. Lower Bound: 해당 Key가 처음으로 나타나는 위치를 찾는 것.
2. Upper Bound: 주어진 값보다 큰 Key 중에서 가장 작은 인덱스를 찾는 것이다. 이를 통해서 해당 Key가 가장 마지막으로 나타나는 위치를 찾을 수 있다.
3. 두 경우에서 Key가 존재하지 않을 경우에는 일반적으로 삽입되어야 할 위치를 반환하도록 알고리즘을 구성한다.

 

 

---

Lower Bound

static int getLowerBound(int[] data, int key){
    int left = 0;
    int right = data.length;

    while(left < right){
        int mid = (left + right) / 2;
        if(data[mid] >= key){
            right = mid;  // 키를 찾은 경우 :  <- 방향으로 right를 당김
        }
        else{
            left = mid + 1;
        }
    }
    return right;
}

 

• data[mid]가 key보다 크거나 같은 경우 : 오른쪽으로 더 이상 탐색할 필요가 없으므로 right를 mid로 업데이트
  • 기존 이분 탐색과 달리 범위를 mid-1로 업데이트 하지 않고 mid로 업데이트해서 mid의 값은 남겨둔다. (같은 경우까지이므로 후보군이 될수있음)
  • 이렇게 되면 mid가 key와 같은 값이더라도 key보다 작은 값을 만나기 전 까지 계속해서 왼쪽으로 이동한다.
• data[mid]가 key보다 작은 경우 : 탐색 범위를 오른쪽으로 좁히기 위해 left를 mid + 1로 업데이트

 

Lower Bound를 구하는 과정

Index	0	1	2	3	4	5	6	7	8
Key	1	2	3	3	3	3	4	4	5
	left				mid				right

 

 

Index	0	1	2	3	4	5	6	7	8
Key	1	2	3	3	3	3	4	4	5
	left		mid		right

 

 

Index	0	1	2	3	4	5	6	7	8
Key	1	2	3	3	3	3	4	4	5
	left	mid	right

 

 

Index	0	1	2	3	4	5	6	7	8
Key	1	2	3	3	3	3	4	4	5
			left, right

 

Index	0	1	2	3	4	5	6	7	8
Key	1	2	3	3	3	3	4	4	5
			Min, Lower Bound

 

---

Upper Bound

static int getUpperBound(int[] data, int key){
    int left = 0;
    int right = data.length;

    while(left < right){
        int mid = (left + right) / 2;
        if(data[mid] <= key){ // 키를 찾은 경우 :  -> 방향으로 left를 당김
            left = mid + 1;
        }
        else{
            right = mid;
        }
    }
    return right;
}

• data[mid]가 key보다 큰 경우: 탐색 범위를 왼쪽으로 좁히기 위해 right를 mid로 업데이트
• data[mid]가 key보다 작거나 같은 경우 : 왼쪽으로 더 이상 탐색할 필요가 없으므로 left를 mid+1로 업데이트
  • key와 같은 경우라도 mid+1로 left를 업데이트 해서 key보다 큰 값을 만날 때 까지 탐색을 진행할 수 있다.
  • 이렇게 되면 mid가 key와 같은 값이더라도 key보다 큰 값을 만나기 전 까지 계속해서 오른쪽으로 이동한다.

 

Upper Bound를 구하는 과정

Index	0	1	2	3	4	5	6	7	8
Key	1	2	3	3	3	3	4	4	5
	left				mid				right

 

Index	0	1	2	3	4	5	6	7	8
Key	1	2	3	3	3	3	4	4	5
						left	mid		right

 

Index	0	1	2	3	4	5	6	7	8
Key	1	2	3	3	3	3	4	4	5
						left, mid	right

 

Index	0	1	2	3	4	5	6	7	8
Key	1	2	3	3	3	3	4	4	5
							left, right

 

 

Index	0	1	2	3	4	5	6	7	8
Key	1	2	3	3	3	3	4	4	5
						Max	Upper Bound

 

 

---

public static void main(String[] args) {
    int[] data = {1, 2, 3, 3, 3, 3, 4, 4, 5};

    int key = 3;

    int lowerBound = getLowerBound(data, key); //2
    int upperBound = getUpperBound(data, key); //6
    int min = lowerBound;
    int max = upperBound - 1;
    System.out.println(min); //2
    System.out.println(max); //5


}

 

 

 

 

---

문제 : 랜선 자르기 (백준 1654)

 

 

결국 해당 문제는 N개의 랜선 중, 최대 길이에 해당하는 랜선만큼의 범위에서 얼마만큼을 잘랐을 때 K개를 만족할 것이냐를 물어보는 것이다.

위의 예제 입력에 따르면 우리는 1~802 길이의 범위에서 11개의 랜선이 되도록 하는 값의 최대값을 찾아야 하는 것이다.

따라서 위에서 설명했던 Upper Bound의 개념을 사용하여 1~802를 이분 탐색하여 Key가 11을 만족하는 최대값을 찾아내야 한다.

 

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int k = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());

        long max = Integer.MIN_VALUE;
        int[] data = new int[k];
        for(int i = 0; i < k; i++){
            st = new StringTokenizer(br.readLine());
            data[i] = Integer.parseInt(st.nextToken());
            max = Math.max(max, data[i]);
        }

        long left = 0;
        long right = max + 1;

        while(left < right){
            long mid = (left + right) / 2;
            long value = 0;
            for(int i = 0; i < k; i++){
                value += (data[i] / mid);
            }
            if(value >= n){
                left = mid + 1;
            }
            else{
                right = mid;
            }
        }

        System.out.println(left - 1);

    }
}

 

1. 범위 계산 : 탐색 범위는 주어진 랜선의 최대 길이만큼이다. 따라서 max를 계산한다.

2. 탐색 범위 설정 : 유의할 점은 right에 max가 아닌 max + 1을 할당한다는 것이다. 왜냐하면 Upper Bound 값에서 -1을 한 값이 우리가 구하려는 최대값일 것이기 때문이다.

3. 이분 탐색 : left와 right의 중간점인 mid에서, 모든 랜선을 해당 길이로 나누어 보았을 때의 수치를 계산한다. 해당 수치가 Key가 될 것이고, mid로 계산한 Key에 따라서 탐색 범위를 재설정한다. 이분 탐색 시 최대값을 구해야 하므로 Upper Bound를 탐색한다.

4. 결과 계산 : 계산된 Upper Bound에서 -1을 하여 K개의 랜선을 만들 수 있는 최대 랜선 길이를 얻어낸다.

 

 

---

이진 탐색 트리(Binary Search Tree)

 

https://en.wikipedia.org/wiki/Binary_search_tree

 

 

탐색을 위한 트리로서 사용되는 이진 탐색 트리가 있다. 해당 자료구조는 정렬된 형태의 이진 트리로서, 탐색을 위한 트리로 유용하게 사용될 수 있다. 즉, 이진 탐색의 개념을 트리 형태의 구조에 접목한 자료구조이다.

 

<함께 보기>
https://sjh9708.tistory.com/204

[자료구조/JAVA] 트리 (2) : 이진 탐색 트리(Binary Search Tree, BST)