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

안녕하세요. BlockDMask 입니다.

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

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

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

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

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

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

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

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

입니다.

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

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

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;
    
           }
       }
       return false;
   }

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) { //key 값이 mid 의 값보다 작을때(왼쪽으로)
           return BinarySearch(arr, start, mid - 1, key);
           
       } else {  //key 값이 mid 의 값보다 작을때(왼쪽으로)
           return BinarySearch(arr, mid + 1, end, key);
           
       }
   }

   
   

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

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


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


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




#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;
}

<출처>

http://www.cplusplus.com/reference/algorithm/binary_search/

https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%EA%B2%80%EC%83%89_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98