탐색
선형 탐색
앞에서부터 하나씩 보면
사물함 12칸에 번호표가 하나씩 들어 있습니다. 칸 번호는 0번부터입니다. 열 수 있는 칸은 다음 칸 하나뿐입니다
찾는 번호 4
먼저 맞혀 보세요. 번호표 4는 몇 번 칸에 들어 있을까요?
연 칸 0
내 예상 · 실제 8번 칸 → 달랐어요
칸을 0번 열어 8번 칸에서 번호표 4를 찾았습니다. 번호표가 섞여 있어서 열어 보기 전에는 어느 칸인지 알 수 없었습니다.
0번 칸 → 1번 칸 → … → 8번 칸찾을 때까지 앞에서부터 한 칸씩 열었습니다.
앞에서부터 하나씩 · 1,000,000칸1,000,000번
절반씩 버리기 · 1,000,000칸20번
앞에서부터 하나씩 열어 보는 방법 = 선형 탐색
- 운이 좋으면 — 첫 칸에서 끝난다
- 없으면 — 12칸을 다 열어야 확실하다. 칸이 N개면 N번. 이걸
O(N)이라고 적는다
번호표가 섞여 있어도 되는 방법
- 정렬이 필요 없다 — 앞 칸부터 열면 섞여 있어도 놓치지 않는다. 건너뛰어 열면 놓칠 수 있다
- 한 번만 찾을 때 — 줄을 세우는 데만 12칸에 약 43번이 든다. 그냥 열면 많아야 12번이다
- 여러 번 찾을 때 — 한 번 줄을 세워 두면 절반씩 버리는 방법으로 바꿀 만하다
코드는 칸 번호를 하나씩 올리는 반복문이 전부다
다음을 눌러 한 줄씩 넘기며 지나간 칸이 쌓이는 걸 보세요. 번호표 4를 찾아 멈춥니다.
70
31
112
53
94
25
86
127
48
109
610
111
i
다음을 눌러 한 줄씩 넘겨 보세요
i = 0
linear_search.py
- 1def linear_search(arr, target):
- 2 for i in range(len(arr)):
- 3 if arr[i] == target:
- 4 return i
- 5 return -1
0 / 19
i— 지금 여는 칸 번호. 0번부터 하나씩 올라간다arr[i] == target— 칸 안 번호표가 찾는 번호와 같은지 본다. 같으면 바로i를 돌려준다return -1— 끝까지 열어도 없으면 -1 을 돌려준다
번호표가 [4, 9, 2, 7] 인 사물함에서 7 을 찾습니다. 칸을 몇 번 열까요?
못 찾았는데 에러가 나거나 한 줄인데 느리다
arr.index(x)— 없으면 -1 이 아니라ValueError가 난다. 13을 찾으면list.index(x): x not in list로 멈춘다- 같은 번호가 여럿이면 — 첫 칸만 돌려준다.
[3, 8, 3]에서 3 은 0번 칸이다 x in arr— 한 줄이지만 속은 같은 선형 탐색이다. 10만 칸에서 맨 끝 번호를 2천 번 찾으면 리스트는 약 1초,set은 약 0.00006초가 걸렸다. 컴퓨터마다 다르다
문제에서 이 말이 보이면
정렬돼 있지 않다한 번만 찾는다N 이 작다
다음 장에서는 줄이 정렬돼 있을 때 절반씩 버리며 찾는 이분 탐색을 봅니다.