검색과 정렬

이진검색

이진검색은 오름차순이든 내림차순이든 상관없이 배열에 정렬 되어있어야함.
점근적 표기법을 사용하기 때문에 데이터가 짝수인지 홀수인지 상관없이 (홀수 일 때 올림을 할지 내림을 할지 상관없이) 데이터의 절반을 구한다.

이진 검색의 시간복잡도

연결리스트에서는 이진검색 못함

가운데의 데이터를 꺼내지 못하기 때문.
하지만 무조건 이진검색이 순차검색보다 낫다고는 할 수 없다. 이진검색은 정렬이 되어 있어야 하는 전제 하에 가능하지만 순차검색은 그러지 않아도 된다. 단순히 정렬이 되어있을 때 순차검색을 할 필요는 없다는 것을 의미.