[C++] Binary Search 알고리즘

오직 정렬되어씨는 Data값에서 Binary search를 쓰면 더 빨리 찾을 수 있다.

일반적인 탐색은 O(n)이 걸리지만 Binary search는 O(log n)이 된다.

 

<재귀 코드>

#include <iostream>
#include <unordered_map>
using namespace std;

int vect[8] = { 1,1,2,5,7,9,15,20 };
int target = 7;

void binary_search(int start, int end) {
    int mid = (start + end) / 2;
    if (start > end) {
        cout << "못찾음";
        return;
    }
    if (vect[mid] == target) {
        cout << mid << "index";
        return;
    }
    if (vect[mid] < target) {
        binary_search(mid + 1, end);
    }
    else {
        binary_search(start, mid - 1);
    }
}

int main() {

    binary_search(0, 7);

    return 0;
}

 

<while문 코드>

#include <iostream>
#include <unordered_map>
using namespace std;

int vect[8] = { 1,1,2,5,7,9,15,20 };
int target = 7;

int main() {

    int start = 0;
    int end = 7;
    while (1) {
        int mid = (start + end) / 2;
        if (start > end) {
            cout << "못찾음";
            return 0;
        }
        if (vect[mid] == target) {
            cout << mid << "index";
            return 0;
        }
        if (vect[mid] < target) {
            start = mid + 1;
        }
        else {
            end = mid - 1;
        }
    }

    return 0;
}