앞서 언급했듯이 배열 검색은 배열에 특정 값이 있는지 알아본 후, 있다면 어떤 인덱스에 있는지 찾는 것이다.

어떻게 보면 읽기와 반대다. 읽기는 컴퓨터에 인덱스를 제공하고 그 인덱스에 들어 있는 값을 반환하라고 요청한다. 반면 검색은 컴퓨터에 값을 제공하고 그 값이 들어 있는 인덱스를 반환하라고 요청한다.

비슷해 보이지만 효율성 측면에서 어마어마하게 다르다. 인덱스에서 읽기는 컴퓨터가 어떤 인덱스든 바로 가서 인덱스에 있는 값을 찾을 수 있으니 매우 빠르다. 이와 달리 검색은 컴퓨터가 특정 값으로 바로 갈 수 없으니 오래 걸린다.

이것이 컴퓨터의 중요한 특징이다. 컴퓨터는 모든 메모리 주소에 한 번에 접근하지만 각 메모리 주소에 어떤 값이 있는지 바로 알지 못한다.

예를 들어 앞서 봤던 과일과 야채 배열 예제를 보자. 컴퓨터는 각 셀에 실제 어떤 내용이 들어 있는지 바로 알 수 없다. 컴퓨터에서 배열은 꼭 다음처럼 보인다.

▲ 그림 1-6

배열에서 과일을 찾으려면 컴퓨터는 각 셀을 한 번에 하나씩 조사하는 방법밖에 없다.