알고리즘 : 분할정복법 - 이분탐색

알고리즘에서 필요한것 중 하나는 내가 원하는 데이터를 얼마나 빠르게 찾을 수 있는가 입니다.

이를 위해 여러가지 탐색방법이 존재하며, 이 중 이분탐색에 대해 알아보도록 하겠습니다.

 

 

 

이분탐색이란?

이분탐색은 말 그대로 반씩 탐색하는것을 말합니다.

기존의 탐색방법은 하나의 데이터를 찾기 위해 모든 데이터를 확인해야 했고,

이 때문에 O(n) 의 시간복잡도를 갖게 되었습니다.

하지만, 이분탐색의 경우, 분할정복법을 사용하여 중간지점만을 확인

원하는 값이 없는 절반은 제외하는 식으로 계산하기 때문에

log₂n의 꼴, 즉 O(log n)의 시간복잡도를 갖게 되었습니다.

 

 

 

 

이분탐색을 위한 조건

이분탐색은 중간값과 탐색값을 비교하여 탐색값보다 작거나 큰 값 절반을 제외하는 방법이기 때문에, 

그 절반이 확실하게 탐색값보다 작거나 큰 지 보장할 수 있어야 합니다.

이를 위해 이분탐색을 위한 데이터는 반드시 정렬 되어있어야 합니다. 

 

 

 

 

이분탐색 사용하기

number binary_search(number target, number low, number high, number[] array)
{
    if(low >= high) return -1;
    number mid = (low + high)/2;
    if(array[mid] == target) return mid;
    else if(array[mid]>target) return binary_search(target,low,mid-1,array);
    else return binary_search(target,mid+1,high,array);
}

이분탐색의 구현은 간단합니다.

시작점과, 끝점, 그리고 찾는대상, 데이터를 매개변수로 두고,

시작점과 끝점을 사용해 중간지점을 구합니다.

중간점과 같으면 탐색 지점을 반환,

중간점보다 작으면 시작점과 중간점 사이를 탐색

중간점보다 크면 중간점과 끝점 사이를 탐색

그리고 끝까지 못찾으면 -1, 즉 인덱스에 없는 숫자를 반환하면 됩니다.

 

이러한 과정을 통해 정렬된 데이터라는 전제하에,

훨씬 빠른 탐색결과를 도출할 수 있습니다.