선형 탐색 — 창고를 처음부터 뒤지기

주문 번호 ORD-20260819-0042 의 배송지를 확인해야 합니다. 주문 목록은 그냥 들어온 순서대로 쌓여 있습니다.

방법은 하나뿐입니다. 맨 앞에서부터 하나씩 보면서 번호가 맞는지 확인한다. 이것을 선형 탐색(linear search) 또는 순차 탐색이라고 부릅니다.

너무 당연해서 알고리즘 같지도 않죠? 그런데 이것이 여러분 쇼핑몰이 느려지는 원인 1위입니다.

🎮 창고 순차 탐색

아래에서 상품을 골라 찾아 보세요. 로봇이 선반을 한 칸씩 지나갑니다. 개수를 늘렸을 때 걸음 수가 어떻게 변하는지, 그리고 없는 상품을 찾으면 무슨 일이 벌어지는지 꼭 해 보세요.

그래도 선형 탐색을 써야 할 때

느리다고 나쁜 알고리즘은 아닙니다. 이럴 때는 선형 탐색이 정답이에요.

• 데이터가 적을 때 — 100개짜리 목록에 인덱스를 만드는 게 더 손해입니다.
• 정렬이 안 되어 있고, 한 번만 찾을 때 — 정렬하는 데 O(n log n)이 드는데 한 번 찾자고 정렬하면 손해예요.
• 조건이 복잡할 때 — "이름에 '무선'이 들어가고 재고가 3개 이상인 것"은 인덱스로 못 찾습니다. 결국 다 훑어야 해요.

조금이라도 빠르게 — 실무의 잔기술

알고리즘 자체는 그대로 O(n)이지만, 실제 체감 속도를 줄이는 방법들이 있습니다.

• 찾으면 즉시 멈추기 — break 또는 return. 끝까지 도는 코드는 평균 2배 느립니다.
• 자주 찾는 것을 앞으로 — 인기 상품을 목록 앞에 두면 평균 걸음이 확 줄어듭니다. (16강 캐시의 기본 아이디어예요.)
• 싼 조건을 먼저 검사 — 재고 >= 3(빠름)을 "무선" in 이름(느림)보다 먼저 쓰면 대부분 일찍 걸러집니다.