또다시 찾기에 실패했으므로 컴퓨터는 다음 셀로 이동한다.

▲ 그림 1-10

드디어 "dates"를 찾았고 이제 "dates"가 인덱스 3에 있음을 안다. 찾고 있던 값을 발견했으니 컴퓨터는 배열의 다음 셀로 이동해서 검색을 계속할 필요가 없다.

예제에서 컴퓨터는 찾으려던 값을 발견할 때까지 4개의 셀을 확인하므로 이 연산에는 총 4단계가 걸렸다고 할 수 있다.

2장 알고리즘이 중요한 까닭에서 다른 배열 검색 방법을 소개하겠지만 이와 같은 검색 연산, 즉 컴퓨터가 한 번에 한 셀씩 확인하는 방법을 선형 검색이라 부른다.

그렇다면 컴퓨터가 배열에서 선형 검색을 수행하는 데 필요한 최대 단계 수는 얼마일까?

("elderberries"처럼) 찾고 있는 값이 배열의 마지막 셀에 있다면 컴퓨터는 이 값을 발견할 때까지 배열의 모든 셀을 검색해야 한다. 또한, 찾고 있는 값이 배열의 어떤 셀에도 없으면 마찬가지로 모든 셀을 검색해야 비로소 배열에 값이 없다고 확신할 수 있다.

따라서 5개의 셀로 이뤄진 배열에서 선형 검색에 걸리는 최대 단계 수는 5다. 500개의 셀로 이뤄진 배열이라면 선형 검색에 걸리는 최대 단계 수는 500이다.

달리 표현하면 N개의 셀로 이뤄진 배열은 선형 검색에 최대 N개의 단계가 필요하다고 말할 수 있다. 이때 N은 어떤 수든 넣을 수 있는 단순한 변수다.

어쨌든 검색은 읽기보다 분명히 덜 효율적이다. 읽기는 배열이 얼마나 크든 항상 한 단계만 걸리지만 검색에는 많은 단계가 걸릴 수 있다.

다음으로는 삽입 연산을 알아보자.