Binary Search (이진 탐색)

Binary Search

• 데이터가 정렬되어 있는 경우에서, 탐색 범위를 두 부분으로 나누어 가면서 원하는 원소를 찾는 방법
• 시간복잡도: O(log N) // 모두 탐색을 하는 경우에는 O(N)

---

이진 탐색의 과정

1. 탐색 범위를 설정 (start, end지점)

2. 탐색 지점(mid) 설정 후 찾는 값(key)와 비교한다.

   mid = (start+end) /2

3. mid == key 일 때의 해당 값을 찾는다.

   mid > key 이면, [start, mid-1] 로 탐색 범위 수정

   mid < key 이면, [mid+1, end] 로 탐색 범위 수정

4. start > end가 될 때까지, 2~3 과정을 반복

---

이진 탐색  코드

1. 반복문을 사용한 방법

int BinarySearch(int arr[], int key) {
    int start = 0;
    int end = arr.length - 1;
    int mid;

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

        if (arr[mid] == key)
            return mid;
        else if (arr[mid] > key)
            end = mid - 1;
        else
            start = mid + 1;
    }
    return -1;
}

 

2. 재귀함수를 사용한 방법

int BinarySearch(int arr[], int key, int start, int end) {
    if (start > end)
        return -1;

    int mid = (start + end) / 2;
    if (arr[mid] == key)
        return mid;
    else if (arr[mid] > key)
        return BSearchRecursive(arr, key, start, mid-1);
    else
        return BSearchRecursive(arr, key, mid+1, end);
}

 

3. C++ STL <algorithm>을 사용한 방법

: 찾고자 하는 key 값의 유무를 bool의 형태로 알려줌

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {

	vector<int> v = { 1,2,4,8,9,10 }; // 정렬된 데이터

	cout << binary_search(v.begin(), v.end(), 5); // 0(false)
	cout << binary_search(v.begin(), v.end(), 8); // 1(true)

	return 0;
}

---

이진 탐색  기반 응용 코드

1. lower_bound / upper_bound

- lower_bound : k보다 크거나 같은 값 중에서 가장 작은 원소의 위치

public static int lowerBound(int[] arr, int l, int r, int key){
    //r은 배열의 사이즈 N을 넣어준다. 
    int m;
    while(l<r){
        m = (l+r)/2;
        if(arr[m]< key) l = m+1;
        else r = m;
    }
    return r;
}

- upper_bound : k보다 큰 원소 중에서 가장 작은 원소의 위치

public static int upperBound(int[] arr, int l, int r, int key){
    int m;
    while(l<r){
        m = (l+r)/2;
        if(arr[m]<=key) l=m+1;
        else r=m;
    }
    return r;
}

- C++ STL <algorithm>에 저장, 반복자의 형태로 반환

template <class ForwardIt, class T>
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value);

template <class ForwardIt, class T>
ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value);