[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.

• 전반적 내용
  : '바킹독'님의 블로그 중 '[실전 알고리즘] 0x13강 - 이분탐색'

1. 이분탐색
2. Parametric Search
3. Q&A
4. 마치며

1. 이분탐색

• 이분탐색
  : 정렬되어 있는 배열에서 특정 데이터를 찾기 위해, 모든 데이터를 순차적으로 확인하는 대신, 탐색 범위를 절반으로 줄여가며 찾는 탐색 방법. O(lg N).

1) 구현

이분탐색을 구현할 때 주의할 점은

1. 주어진 배열은 정렬되어 있어야 한다.

2. 무한 루프에 빠지지 않게 mid값을 결정해야 한다.

int binarysearch(int target){
    int st = 0, en = n - 1;
    while(st <= en){
        int mid = (st + en) / 2;
        if(a[mid] < target) st = mid + 1;
        else if(a[mid] > target) en = mid - 1;
        else return 1;
    }
    return 0;
}

직접 구현 대신 binary_search(a, a + n, t)로 대체 가능.

int lower_idx(int target, int len){
    int st = 0, en = len;
    while(st < en){
        int mid = (st + en) / 2;
        if(a[mid] >= target) en = mid;
        else st = mid + 1;
    }
    return st;
}

int upper_idx(int target, int len){
    int st = 0, en = len;
    while(st < en){
        int mid = (st + en) / 2;
        if(a[mid] > target) en = mid;
        else st = mid + 1;
    }
    return st;
}

직접 구현 대신 lower_bound, upper_bound로 대체 가능

2. Parametric Search

• Parametric Search
  : 조건을 만족하는 최소/최대값을 구하는 문제(최적화 문제)를 결정 문제로 변환해 이분탐색을 수행하는 방법

문제에서 최소/최대 얘기가 있고 범위가 엄청 크다거나 시간복잡도에서 값 하나를 로그로 떨굴 수 있을 때, 고려할 수 있는 방법.

1. 최적화 문제를 결정 문제로 바꿀 수 있는가?

2. 결정 문제로 얻어낸 함수가 감소 혹은 증가함수인가?

3. Q&A

-

4. 마치며

-

[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.

• 전반적 내용
  : '바킹독'님의 블로그 중 '[실전 알고리즘] 0x13강 - 이분탐색'