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