원하는 걸 빠르게 찾기

처음부터 차례로

찾는 가장 쉬운 방법은
처음부터 하나씩 보는 거예요.
'이건가? 아니네.
다음은? 아니네.'
맞을 때까지
계속 넘기는 거죠.
확실하긴 한데,
뒤에 있으면
오래 걸려요.

앞에서부터 하나씩. (찾을 값 13 · 앞에서부터 한 칸씩 확인)

칸이 몇 개 안 되면
괜찮아요.
근데 수천, 수만 개라면?
하나씩 보다간
한참 걸리죠.
더 좋은 방법이 있어요.
줄이 맞아 있을 때 쓰는
똑똑한 방법이에요.

가운데를 펴봐요

줄이 맞아 있으면
이렇게 해요.
가운데를 펴서 봐요.
찾는 값이 그보다 크면
앞쪽 절반은 버려요.
작으면 뒤쪽 절반을 버리고.
한 번 볼 때마다
절반이 사라져요.

가운데를 보고 절반을 버려요. (찾을 값 13 · 없는 절반을 통째로 버림)

한 번에 절반을 버리니까,
남는 게 확 줄어요.
8칸이 4칸,
4칸이 2칸,
2칸이 1칸.
몇 번 만에
딱 한 칸으로 좁혀져요.

하나씩 vs 반씩

둘을 나란히 두고
같은 값을 찾아봐요.
하나씩은
뒤에 있는 값까지
여러 번 봐야 해요.
반씩은
몇 번 만에 끝나죠.
같은 답인데
걸음 수가 확 달라요.

같은 값(13) 찾기, 걸음 수 비교. (하나씩 = 느림 · 반씩 = 빠름)

칸이 많아질수록
차이가 더 벌어져요.
천 개를 하나씩이면
최대 천 번,
반씩이면 열 번이면 돼요.
이 차이가
큰 데이터에선
어마어마해요.

왜 정렬이 먼저일까

반씩 자르기엔
조건이 하나 있어요.
줄이 맞아 있어야 해요.
정렬돼 있어야
'가운데보다 크면 앞은 버려도 돼'가
성립하거든요.
뒤죽박죽이면
절반을 버릴 수가 없어요.

정렬됐을 때만 반씩 자르기가 통해요. (줄 맞음 → 성립 · 뒤죽박죽 → 불성립)

그래서 정렬과 찾기는
짝꿍이에요.
한 번 줄을 세워두면,
그다음부터 찾기가
계속 빨라지니까요.
정돈에 드는 수고가
두고두고 보답받는 거죠.

여기까지 왔어요

찾기는 늘 곁에 있어요.
사전, 전화번호부,
검색창에 친 한 단어.
그 뒤에서
'반씩 자르기' 같은 방법이
빠르게 답을 찾아줘요.
순서, 정렬, 찾기까지
이제 한 줄로 이어졌어요.

순서 → 정렬 → 찾기, 여기까지. (찾기 = 원하는 걸 빠르게 집어내기)

알고리즘이
대단한 게 아니란 걸
이제 알 거예요.
순서를 정하고,
정돈하고,
똑똑하게 찾는 것.
작은 꾀가 모여
큰일을 해내는 거예요.