어떻게 원하는 걸 빠르게 찾기

처음부터 차례로

가장 쉬운 찾기는 처음부터 하나씩 보는 것이다.
'이것인가? 아니다. 다음은? 아니다.' 맞을 때까지 계속 넘긴다.
확실하기는 하지만 찾는 값이 뒤에 있으면 오래 걸려요.

하나씩 찾기를 누르면 앞에서부터 한 칸씩 확인한다. 찾을 값은 13.

칸이 몇 개 되지 않으면 괜찮다.
하지만 수천, 수만 개라면 하나씩 보다가는 한참 걸린다.
더 좋은 방법이 있다. 줄이 맞아 있을 때 쓰는 영리한 방법이에요.

가운데를 편다

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

가운데 보기를 누를 때마다 찾는 값이 없는 절반을 통째로 버린다. 찾을 값은 13.

한 번에 절반을 버리니 남는 것이 확 준다.
8칸이 4칸, 4칸이 2칸, 2칸이 1칸이 된다.
몇 번 만에 딱 한 칸으로 좁혀져요.

하나씩 vs 반씩

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

같은 값(13) 찾기에서 걸음 수를 견준다. 하나씩 = 느림 · 반씩 = 빠름.

칸이 많아질수록 차이는 더 벌어진다.
천 개를 하나씩 보면 최대 천 번이 걸리지만, 반씩 자르면 열 번쯤이면 된다.
이 차이가 큰 데이터에서는 어마어마해요.

왜 정렬이 먼저일까

반씩 자르기에는 조건이 하나 있다. 줄이 맞아 있어야 한다는 것이다.
정렬되어 있어야 '가운데보다 크면 앞쪽은 버려도 된다'가 성립하기 때문이다.
뒤죽박죽이면 절반을 버릴 수 없어요.

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

그래서 정렬과 찾기는 짝이다.
한 번 줄을 세워 두면 그다음부터 찾기가 계속 빨라진다.
정돈에 든 수고가 두고두고 보답받는 셈이에요.

여기까지 온 길

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

순서 → 정렬 → 찾기, 여기까지 왔다. 찾기 = 원하는 것을 빠르게 집어내기.

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