이진 탐색 Binary Search

: 정렬된 자료를 반으로 계속해서 나누어 탐색하는 방법

>> 코드:

int* binarySearch(int key, const int *target, size_t length) {
    int first = 0, last = length - 1, middle = (first + last) / 2;
    while (first <= last) {
        if (target[middle] == key) 	
            return target + middle;
            
        if (target[middle] > key) 
            last = middle - 1;
        else 			
            first = middle + 1;
            
        middle = (first + last) / 2;
    }  	
    
    return NULL;
}

시간 복잡도:

출처: Learning Never Stops