<개인공부>/[Algorithm]

[탐색] 이진탐색 (Binary Search) 구현 방법

사용자 BlockDMask 2017. 10. 9. 09:00
반응형

안녕하세요. BlockDMask 입니다.

알고리즘 코딩 사이트(백준 온라인 저지)에서 '수 찾기' 문제를 풀다가 이진탐색(Binary Search)이 나와서, 

이번 기회에 정리를 해볼까 합니다.


1. 이진탐색(Binary Search) 이란.

  • 이진 탐색 알고리즘(Binary Search Algorithm)오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘 입니다.

  • 오름차순으로 정렬된 리스트의 중간 값을 임의의 값으로 선택하여, 찾고자 하는 Key값과 비교하는 방식으로 돌아가는 알고리즘 입니다.

  • 정렬된 리스트에서만 사용할 수 있다는 단점이 존재합니다.

  • 검색이 될때마다 선형탐색(Linear Search)와는 비교할 수 없게 빨라집니다.

2. 이진탐색(Binary Search)의 시간 복잡도


입니다.

3. 이진탐색(Binary Search)의 구현


이진탐색을 구현하는 방법 : 제가 알고있는 것은 세가지가 있습니다.

  1. 직접 구현 - 반복문을 이용한 이진 탐색

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    //반복문을 이용한 이진탐색을 이용하여 탐색
    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;
     
            }
        }
        return false;
    }
    cs

  2. 직접 구현 - 재귀를 이용한 이진 탐색

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    //재귀를 이용한 이진탐색을 이용하여 탐색
    bool BinarySearch(int *arr, int start, int endint key) {
     
        if (start > endreturn false//key 값이 없을 때
     
        int mid = (start + end/ 2;
     
        if (arr[mid] == key) {    //key 값을 찾았을 때
            return true;
            
        } else if (arr[mid] > key) { //key 값이 mid 의 값보다 작을때(왼쪽으로)
            return BinarySearch(arr, start, mid - 1, key);
            
        } else {  //key 값이 mid 의 값보다 작을때(왼쪽으로)
            return BinarySearch(arr, mid + 1end, key);
            
        }
    }
    cs


  3. STL이용 - binary_search 함수를 이용한 이진 탐색

  4. <algorithm> 해더 파일안에 있는 binary_search 함수를 이용하면 됩니다.


    binary_search 의 기본형은 이러합니다.

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


    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    #include<iostream>
    #include<algorithm>
    using namespace std;
     
    //STL를 이용한 이진탐색을 이용하여 탐색
    int main(void){
        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;
    }
    cs


반응형