2 상자를 이용한 선형 검색

상자 5개 중 하나에는 곰 인형이 들어 있습니다. 어느 상자 속에 곰 인형이 들어 있을까요?

 

1번 상자를 열어 봅니다. 인형이 없네요.

2번 상자를 열어 봅니다. 여기도 인형이 없습니다.

이제 3번 상자를 열어 봅니다. 인형이 있습니다.

세 번 비교해서 인형을 찾았습니다.

이처럼 처음부터 차례로 상자를 열어 데이터를 찾는 방법을 선형 검색이라고 합니다. 운이 좋으면 1번 상자에서 찾을 수 있고, 운이 좋지 않으면 마지막 상자에서 인형을 찾을 수 있습니다.