본문 바로가기
<개인공부>/[Algorithm]

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

by 사용자 BlockDMask 2017. 10. 9.
반응형

안녕하세요. 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


반응형

댓글3

  • .. 2021.03.19 23:21

    아니.. 이진 검색이면 mid - 1, mid +1 로 반복해서 구현할게 아니라 mid를 start / end로 다시 재설정해서 찾아야죠...
    지금 구현하신 코드는 맨 처음만 중앙 값에서 시작하고 이후에는 Linear Search 로 동작합니다.
    비추를 드리고 싶은데 비추버튼이 없네요.
    답글

  • .. 2021.03.19 23:22

    int find(int arr[], int start, int end, int key) {
    while (end - start >= 0) {
    int mid = (start + end) / 2;
    if (arr[mid] == key) {
    // 그 이전에 같은 수가 만약 발견 되면 한번 더 이분탐색.. (배열에 중복된 값 있을 경우)
    if (mid - 1 >= 0 && arr[mid - 1] == key) {
    end = mid;
    continue;
    }
    return mid;
    } else if (arr[mid] > key) {
    end = mid;
    } else {
    start = mid;
    }
    }
    return -1;
    }

    큰 배열에서 두 알고리즘 시간 비교 해보시기 바랍니다.
    답글

    • ㅇㅇ 2021.03.29 15:08

      중복값 고려한거 제외하곤 위의 알고리즘이랑 전혀 다를게 없는데요?