[Algorithm/Java] 이진탐색 Binary Search / UpperBound / LowerBound

BinarySearch : 이진탐색 (이분탐색)

이진탐색은 데이터가 정렬되어 있는 상태에서 원하는 값을 찾아내는 알고리즘이다.
데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는 방식이다.

크기가 100인 배열이 있고, 우리가 찾고자 하는 값이 99번째 인덱스에 들어있는 상황을 가정해 보자.

 

일반적인 반복문을 사용하여 1부터 100까지 반복하면 99번째 반복에서 찾고자 하는 값을 찾을 수 있다. 물론 이 경우 찾고자 하는 데이터가 앞쪽에 있다면 같은 데이터셋에 대하여 탐색 시간이 이분탐색을 이용했을 때보다 빠를 것이다.

 

그런데 만약 데이터의 크기가 1억 개이고, 운이 나쁘게도 우리가 찾고자 하는 값이 99,999,999 번째의 데이터인 경우에는 시간이 매우 오래 걸릴 것이다.

이진탐색을 이용하면 데이터의 위치에 따른 탐색시간의 격차를 줄일 수 있다.

---

1. 시간 복잡도

시간복잡도 :O(logN)

---

2. 이진탐색 핵심 이론

1. 현재 데이터셋의 중앙값을 선택한다.
2. 중앙값과 찾고자 하는 값을 비교한다.
   2-1. 중앙값 > 타깃 데이터 인 경우 : 중앙값을 기준으로 왼쪽 데이터셋을 선택한다. (오른쪽은 버린다.)
   2-2. 중앙값 < 타겟 데이터 인 경우 : 중앙값을 기준으로 오른쪽 데이터셋을 선택한다. (왼쪽은 버린다.)
3. 1~2를 반복하다가 중앙값 = 타겟 데이터 일 때 탐색을 종료한다.

데이터는 항상 정렬되어 있어야 한다.

---

3. 예제

아래와 같이 10개의 데이터가 있는 데이터셋에서 값이 63인 데이터를 찾아보자.

1

12

14

27

33

42

45

52

63

70

1. 중앙값을 찾는다. 
크기가 10이므로 (1+10)/2 = 5 이므로 중앙값은 5번째이다.
-> 중앙값 = 5번째(33)

2. 찾고자 하는 데이터와 중앙값을 비교
타깃 데이터(63) > 중앙값(33) 이므로, 오른쪽 데이터셋을 선택한다.

3. 데이터셋 재설정
이제 6번째(42)부터 10번째(70)까지 탐색한다.

42

45

52

63

70

(위의 과정을 반복한다.)

 

1. 중앙값 설정 : 중앙값 = 52

2. 데이터 비교 :  63 > 52 이므로 오른쪽 데이터셋 선택

3. 데이터셋 재설정 : 9번째(63)부터 10번째(70)까지 2개의 데이터셋이다.

63

70

1.  중앙값 설정 : 다음 데이터셋은 9번째~10번째 이므로 중앙값은 (int)(9+10)/2 이므로 9이다.

2.  데이터 비교 : 타깃 데이터(63) == 중앙값(63) 이므로 탐색 완료!

---

4. 예제 코드

찾고자 하는 데이터가 몇번 인덱스에 있는지 찾는 예제이다.

배열이 정렬되어있지 않다면, 배열을 정렬하고 찾고자하는 값의 인덱스를 찾는다.

public class Test{
    public static void main(String[] args) throws IOException {
        int[] arr = {1,3,4,12,15,34,36,42,51,64,66,70,88,89,94,100}; // 16개

        System.out.println("89가 들어있는 인덱스 : " + search(arr,89)); // 13
        System.out.println("3이 들어있는 인덱스 : " + search(arr,3)); // 1

    }

    private static int search(int[] arr, int target) {
        //start, end, mid는 모두 인덱스 이고, target은 찾고자하는 수 이다.
        int start = 0;
        int end = arr.length-1;

        while(start<=end){
            int mid = (start+end)/2;
            //target이 중앙값보다 클 경우, 오른쪽 선택(start = mid+1로 변경)
            if(arr[mid]<target){
                start = mid+1;
            } //target이 중앙값보다 작을 경우, 왼쪽 선택(end = mid-1로 변경)
            else if(arr[mid]>target){
                end = mid-1;
            }
            else return mid;
        }
        return -1;
    }
}

 

---

5. Collections.binarySearch

자바의 Collection Framework는 binarySearch를 제공한다.
list와 찾고자하는 값을 매개변수로 받는다.
이때, 리스트는 정렬되어있어야 한다.

return

해당 값이 존재한다면, 해당 값의 index를 반환한다.

해당 값이 없다면, 해당 값이 들어갈 위치를 반환하는데, - (index) -1을 반환한다.
ex) 아래 예제에서 5가 들어갈 자리는 3번 인덱스이기 때문에 -3 -1 = - 4를 반환한다.

---

Collections.binarySearch 예제

#4의 예제를 Collection Framework를 이용해서 풀어보자.

public class Test{
    public static void main(String[] args) throws IOException {
        int[] arr = {1,3,4,12,15,34,36,42,51,64,66,70,88,89,94,100}; // 16개

        LinkedList<Integer> list  = new LinkedList<>();
        for (int i : arr) {
            list.add(i);
        }

        Collections.sort(list);
        int ans= Collections.binarySearch(list,5); //-4
        int ans2= Collections.binarySearch(list,89); //13

        System.out.println(ans); //-4 출력
        System.out.println(ans2); //13 출력

    }
}

---

6. Upper Bound 방식과 Lower Bound 방식

이분탐색에는 크게 두가지 방식이 존재한다.

Upper Bound(상한선) 방식과 Lower Bound(하한선) 방식이다.

Upper Bound방식은 특정 값을 초과하는 첫위치를 반환한다.

Lower Bound방식은 특정 값 이상인 첫 위치를 반환한다.

 

예를들면, [1, 2, 3, 4, 5, 5, 6, 7 ] 크기가 8인 배열에서 5를 찾고자 할때 

Upper Bound 방식은 6의 위치(index = 6)를 반환하고 Lower Bound 방식은 첫번째 5의 위치(index=4)를 반환한다.

 

이 두가지 방식의 구분은 중복 값이 있을 때 중요하다.

만약 중복 원소에서 가장 오른쪽 값을 찾으려면 Upper Bound 방식을 통해 구한 값에 -1을 하면 될것이고,

중복 원소에서 가장 왼쪽 값을 찾으려면 Lower Bound 방식으로 구한 값 그 자체가 정답이 된다.

---

Upper Bound 예제

Upper Bound는 구하는 값보다 큰값이 처음으로 나오는 위치를 반환해야 한다. 만약 구하고자 하는 값이 배열의 오른쪽 끝에 위치한다면 마지막 index+1을 반환해야 하기 때문에, max = arr.length-1이 아니라 max=arr.length로 지정해야 한다.

또한, 탐색한 값이 구하는 값보다 크면 큰 값이 최초로 나오는 위치를 찾아야하기 때문에 max = mid로 지정하여 찾아가면 된다.

그리고 마지막에 원하는 값을 찾으면 찾고자하는 값보다 최초로 큰 값의 인덳스를 반환하기 때문에 -1을 하여 반환해야 한다.

public static int upperBound(int[] arr, int value){
    int max = arr.length;
    int min = 0;
    while(min<max){
        int mid = (min+max)/2;
        if(value<arr[mid]){
            max = mid;
        }else{
            min = mid+1;
        }
    }
    return min-1;
}

---

Lower Bound 예제

 Lower Bound는 구하는 값이 처음으로 나오는 위치를 반환해야 한다. 만약 구하고자 하는 값이 arr의 마지막 인덱스의 값보다 클 경우 arr.length를 반환하게 된다. 따라서 처음에 max = arr.length로 지정해야 한다.

또한 탐색한 값이 나오는 최초의 위치를 찾아야 하기 때문에 value가 탐색값보다 클때는 min=mid+1로 변경해줘야 한다.

그리고 마지막에 while문이 종료되면 중복되는 value값중 가장 왼쪽의 인덱스가 min에 저장되어 있게 되고, min을 그대로 반환하면 된다.

public static int lowerBound(int[] arr, int value){
    int max = arr.length;
    int min = 0;
    while(min<max){
        int mid = (min+max)/2;
        if(value > arr[mid]){
            min = mid+1;
        }else{
            max = mid;
        }
    }
    return min;
}