[알고리즘] 이분 탐색(Binary Search)

 

이분 탐색이란?

 

이분 탐색은 이진 탐색, Binary Search 라고도 한다.

순차적 탐색보다 빠른 탐색을 위해 나온 탐색 방법으로 실제로 이분 탐색의 시간복잡도가 순차적 탐색보다 낮다.

 

 

순차 탐색: 리스트 안에 있는 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법이분 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다. 

 

 

 

이분 탐색 방법

 

1. 처음 범위는 인덱스 0부터 끝까지이다. 이 때 중간 인덱스를 mid로 한다.
2. mid의 값와 찾는 원소를 비교한다.
   2-1) 찾는 원소와 mid의 값이 같다면 탐색 종료한다.
   2-2) mid의 값 < 찾는 원소 일 때 left는 mid + 1로 하여 2)를 다시 반복한다.
   2-3) mid의 값 > 찾는 원소 일 때 right는 mid - 1 로 하여 2)를 다시 반복한다.
3. 만약 right > left가 된다면 해당 배열에 찾는 원소가 없는 것이다.

 

 

 

이분 탐색 구현

 

 

반복문 

public static boolean BSearch(int[] arr, int n){
    int left = 0;
    int right = arr.length -1;
    int mid;

    while(left<=right){
        mid = (left+right) /2;
        if(arr[mid] < n) left = mid+1;
        else if (arr[mid]>n) right = mid-1;
        else return true;
    }
    return false;
}

 

 

재귀

public static boolean BSearchRecursive(int[] arr, int n, int left, int right){
    if(left> right) return false;
    int mid = (left+right) / 2;
    if(arr[mid]<n)
        return BSearchRecursive(arr, n, mid+1, right);
    else if(arr[mid]>n)
        return BSearchRecursive(arr, n, left, mid-1);
    else
        return true;
}

 

 

 

시간 복잡도

 

O(log n) -> 범위를 새로 지정할 때마다 탐색 범위가 1/2씩 줄어든다. 

 

 

 

이분 탐색의 두가지 유형

 

1) 어떤 배열에 특정 값이 있는지 없는지를 검사

public static boolean BSearch(int[] arr, int n){
    int left = 0;
    int right = arr.length -1;
    int mid;

    while(left<=right){
        mid = (left+right) /2;
        if(arr[mid] < n) left = mid+1;
        else if (arr[mid]>n) right = mid-1;
        else return true;
    }
    return false;
}

 

 

 

특정 input 값이 배열에 있는지 없는지를 알아내는 것이다.

이 방식을 위해 배열은 오름차순으로 정렬되어야 한다.

while(left<=right) 일 때 mid값은 중간값으로 계속 초기화해준다.

중간값 mid가 찾는 값이라면 바로 true를 리턴해주고 아니라면 두 포인터 값을 mid 중심으로 바꿔준다.

 

 

 

 

2) parametric search

 

이분 탐색을 응용하여 최댓값이나 최소값을 구하는 방식이다. 특정 input 이 주어지지 않는다.

주어진 값들을 배열에 담고 정렬하는거 까지는 동일하다.

다만, input이 없기에 start는 1, end는 배열 마지막 값(가장 큰 값), mid는 그 중간 값으로 임의로 잡아줘야 한다.

 

ex) 백준 1654(랜선 자르기), 2805(나무 자르기)

 

static long BSearch(){
    long left = 1; // 랜선 길이는 자연수
    long right = arr[k-1];
    while(left<=right){
        long mid = (left+right)/2; // 자르는 길이
        int cnt = 0;
        for(long length : arr){
            cnt += length / mid;
        }
        if(cnt >= n){ // 자른 개수가 n보다 같거나 크면
            left = mid+1; // 자르는 길이를 더 크게 해줘야 함
        }else{ // 자른 개수가 n보다 작으면
            right = mid-1; // 자르는 길이를 더 작게 해줘야 함
        }
    }
    return right;
}

 

 

 

UpperBound & LowerBound

 

 

upper bound

정렬된 숫자들 중에 목표값보다 높은 숫자가 처음 등장하는 인덱스 값을 반환한다.

   static int upperBound(int x) {
        int start = 0;
        int end = arr.length - 1;

        while (start <= end) {
            int mid = (start + end) / 2;
            if (arr[mid] > x) end = mid - 1;
            else start = mid + 1;
        }
        return start;
    }

 

 

lower bound

정렬된 숫자들 중에 목표값이 처음 등장하는 인덱스 값을 반환한다.

    static int lowerBound(int x) {
        int start = 0;
        int end = arr.length - 1;

        while (start <= end) {
            int mid = (start + end) / 2;
            if (arr[mid] >= x) end = mid - 1;
            else start = mid + 1;
        }
        return start;
    }