개념

이진 검색 알고리즘 - 위키백과, 우리 모두의 백과사전

처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다.

검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있다.

Python

import random

def binarySearch(a, v, left, right):
    if left > right:
        return False
    mid = (left+right)//2
    if v < a[mid]:
        return binarySearch(a, v, left, mid-1)
    elif a[mid] < v:
        return binarySearch(a, v, mid+1, right)
    else:
        return mid

n = 20
a = [random.randrange(0, 60) for _ in range(n)]
a.sort()
v = a[random.randrange(0, n)]

print("array = \\n", *a)
print("\\n {} is at {}".format(v, binarySearch(a, v, 0, n-1)))

C++

algorithm 헤더파일에서 binary_search함수를 제공하지만 이 함수는 있느냐, 없느냐의 여부만 판단해서 Bool값을 리턴한다.

아래의 소스코드에서는 둘다 사용했다.

#include <algorithm>
#include <ctime>
#include <iostream>
#include <random>

using namespace std;

namespace custom {
int binary_search(int* a, int size, int v) {
    int left = 0;
    int right = size - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (v < a[mid])
            right = mid - 1;
        else if (a[mid] < v)
            left = mid + 1;
        else
            return mid;
    }

    return -1;
}
}  // namespace custom

int main() {
    mt19937 mt((unsigned int)time(nullptr));
    uniform_int_distribution<int> gen(0, 79);

    int n = 20;
    uniform_int_distribution<int> rnd_idx(0, n - 1);

    int* a = new int[20];
    for (int i = 0; i < n; i++) {
        a[i] = gen(mt);
    }
    sort(a, a + n);
    cout << " array = \\n";
    for (int i = 0; i < n; i++) {
        cout << a[i] << ' ';
    }
    cout << "\\n\\n";

    int idx;
    int v = a[rnd_idx(mt)];
    cout << "Is " << v << " in array? ... ";
    cout << (binary_search(a, a + n, v) ? "YES\\n" : "NO\\n");

    cout << v << " is at " << custom::binary_search(a, n, v);
    cout << '\\n';
}

array = 
1 3 17 17 19 20 21 24 34 42 55 55 70 71 73 77 78 78 79 79

Is 21 in array? ... YES
21 is at 6

back_to_top