📌 알고리즘 - 이진탐색 개념

이진탐색이란?

이진탐색이란 데이터가 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘이다.

배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교한다.
데이터가 오름차순으로 정렬돼있다고 가정했을 때, X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로, X가 중간값보다 크면 배열의 우측의 데이터들을 대상으로 다시 탐색한다. 동일한 방법으로 다시 중간의 값을 임의로 선택하고 비교한다. 해당 값을 찾을 때까지 이 과정을 반복한다.

이진탐색의 시간 복잡도

$O(\log{N})$

이진탐색의 구현

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 함수를 이용한 이진탐색

// 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 (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;
}