정렬된 배열(ordered array)은 배열과 거의 같다. 단지 그 값이 항상 순서대로 있어야 한다는 점이다. 값을 추가할 때마다 배열의 값이 정렬된 상태가 되도록 한다. 하지만 이런 순서를 지키기 위해서는 여러 단계가 필요하다. 항상 실제 삽입 전에 검색을 먼저 수행해서 삽입할 정확한 위치를 알아내야 한다. 이것은 삽입에 있어서 효율을 많이 떨어트리게 된다. 하지만 정렬된 배열의 강력함은 검색 연산에서 드러난다. 배열과 정렬된 배열을 선형 검색으로 검색을 시도하면 정렬된 배열의 장점은 값이 없을 경우 더 빨리 멈출 수 있다는 점 밖에는 없다. 찾으려는 데이터가 발견되지 않고 더 큰 데이터가 나타날 때 정렬된 배열은 바로 멈출 수 있기 때문이다. 대단한 차이가 없어 보인다. 하지만 정렬된 배열에는 알고..
