[알고리즘 개념 정리] 이진 탐색 Binary Search c++

[알고리즘 개념 정리] 이진 탐색 Binary Search c++

탐색 알고리즘 중 하나

• 오름차순으로 정렬된 리스트에서 특정한 위치를 찾는 알고리즘
• 오름차순으로 정렬된 리스트의 중간 값을 임의의 값으로 선택하여, 찾고자 하는 Key 값과 비교하는 방식으로 돌아가는 알고리즘
• 정렬된 리스트에서만 사용할 수 있음 ⇒ 단점
• 검색할 떄마다 선형탐색과는 비교할 수 없는 속도 == logN(밑2)

구현 방법1_직접 구현

bool binarySearch(int *arr, int len, int key) {
        int start = 0;
        int end = len - 1;
        int mid;

        while(end - start >= 0) {
                mid = (start + end) / 2; // 중앙 값

                if(arr[mid] == key) { // key 값을 찾았을 때
                        return true;
                }
                else if(arr[mid] > key) { // key 값이 mid의 값보다 작을때 (왼쪽으로)
                        end = mid - 1;
                }
                else { // key 값이 mid의 값보다 클 때(오른쪽으로)
                        start = mid + 1;
                }
        }
}

구현 방법2_재귀

bool binarySearch(int *arr, int start, int end, int key) {
        if(start > end) return false; // key 값이 없을 때
        int mid = (start+end) / 2;

        if(arr[mid] == key) { // key 값을 찾았을 때
                return true;
        } else if (arr[mid] > key) {
                return binary
        } else {
                return binarySearch(arr, mid + 1, end, key);
        }
}

구현 방법3_STL이용

• <algorithm> 헤더 파일 안에 있는 binary_search 함수 이용

    template <class ForwardIterator, class T>
            bool binary_search(ForwardIterator first, ForwardIterator last, const T& val)

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
        int n = 100;
        int arr[n];

        for(int i = 0; i < n; i++) {
                arr[i] = i;
        }

            cout << "exist : " << binary_search(arr, arr+n, 70) << endl;
        return 0;
}

 

lower_bound

• binary search 기반의 탐색 방법 ⇒ 배열 또는 리스트가 정렬 되어있어야 한다.
• lower_bound는 찾으려 하는 key값이 "없으면" key 값보다 큰 가장 작은 정수 값을 찾는다.
• 같은 원소가 여러개 있어도 상관 없으며, 항상 유일한 해를 구할 수 있다.
• 구간이 [start, end]인 배열이 있을 때, 중간위치의 index를 mid라고 하면 arr[mid-1] < key 이면서 arr[mid] >= key 인 최소의 m 값 을 찾으면 된다.

lower_bound 직접 구현 코드

/**
* n개로 이루어진 정수 집합에서 원하는 수 k 이상인 수가 처음으로 등장하는 위치를 찾으시오
**/
#include <iostream>
using namespace std;

int mylower_bound(int *arr, int n, int key) {
        int start = 0;
        int end = n;

        int mid = n;
        while(end - start > 0) { // start가 end와 같지 않고, 넘지 않을 때
                mid = (start+end) / 2; // 중앙 index

                if(arr[mid] < key) { // key 값이 중앙 값보다 크면
                        start = mid + 1; // mid보다 오른쪽으로
                } else { // key 값이 중앙값보다 작거나 같으면
                        // mid 포함 왼쪽 (포함하는 이유는 key 값과 같은게 없을 때 큰수중 가장 작은 값을 위해)
                        end = mid; 
                }
        }

        return end+1;
}

STL 이용 구현 코드

template <class ForwardIterator, class T>
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val);

/**
* n개로 이루어진 정수 집합에서 원하는 수 k 이상인 수가 처음으로 등장하는 위치를 찾으시오
**/

#include <iostream>
#include <algorithm>

using namespace std;

int main() {

        int arr[10] = {1, 2, 4, 5, 6, 6, 7, 7, 7, 9};

        cout << "lower_bound(6) : " << lower_bound(arr, arr + 10, 6) - arr + 1 << endl;

        return 0;
}

 

upper_bound

(같은 값이 아닌) key 값을 초과하는 가장 첫번째 원소의 위치

• lower_bound와 반대개념
• key값을 초과하는 가장 첫 번째 원소의 위치를 구하는 것
• 구간이 [start, end]인 배열이 있을 떄, 중간위치의 index를 mid라고 하면, arr[mid-1] <= key 이면서 arr[mid] > key 인 최소의 m 값 을 찾으면 된다. (m≥2)

---

Reference

• https://blockdmask.tistory.com/167
• https://blog.hexabrain.net/246
• https://blockdmask.tistory.com/168