더북(TheBook)

코드 2-1 이진 검색을 사용하여 정렬된 배열 검색하기

public static bool Contains(uint[] array, uint lookFor) {
    int start = 0;
    int end = array.Length - 1;
    while (start <= end) {
        int middle = start + ((end - start) / 2);  → 중간 지점을 찾아서 오버플로가 일어나는 상황을 방지한다.
        uint value = array[middle];
        if (lookFor == value) {
            return true;
        }
        if (lookFor > value) {
            start = middle + 1;    → 이 범위의 왼쪽 절반을 삭제한다.
        } else {
            end = middle - 1;    → 이 범위의 오른쪽 절반을 삭제한다.
        }
    }
    return false;
}

여기서 우리는 세다트 알고리즘보다 훨씬 빠른 알고리즘인 이진 검색을 구현했다. 이제 이진 검색이 어떻게 반복을 이용한 방법보다 더 빠를 수 있는지 이해하게 되었다. 따라서 이제부터는 유명한 빅오(Big-O) 표기법에 대해 생각해 볼 수 있다.

신간 소식 구독하기
뉴스레터에 가입하시고 이메일로 신간 소식을 받아 보세요.