코드 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) 표기법에 대해 생각해 볼 수 있다.

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