소개
수학자이면서 싱어송라이터인 사람들을 우연히 만나게 됐어요.
이들은 좋아하는 숫자마다 노래를 하나씩 써 두었는데, 짐작하겠지만 좋아하는 숫자가 아주 많아요 (0이나 73, 6174처럼요).
가장 좋아하는 숫자의 노래를 듣고 싶어졌지만, 노래가 워낙 많아서 알맞은 노래를 찾는 데는 시간이 좀 걸릴 수 있어요.
다행히 이들은 노래를 제목순으로 정렬한 재생 목록으로 정리해 두었어요. 제목은 그 노래가 다루는 숫자, 그 자체예요.
이진 탐색 알고리즘을 쓰면 제목만으로도 원하는 노래를 빠르게 찾을 수 있다는 걸 알게 돼요.
지침
이번 과제는 이진 탐색 알고리즘을 구현하는 거예요.
이진 탐색 알고리즘은 배열을 절반으로 계속 나누면서, 찾고 있는 항목이 들어 있는 절반만 남기는 방식으로 항목을 찾아요.
이렇게 하면 항목을 찾을 때까지, 또는 가능한 모든 위치를 없앨 때까지 항목이 있을 수 있는 위치를 빠르게 좁혀 나갈 수 있어요.
이진 탐색은 배열이 정렬되어 있을 때만 동작해요.
알고리즘은 다음과 같아요:
-
정렬된 배열의 중간 원소를 찾아서, 찾고 있는 항목과 비교해요.
- 중간 원소가 찾는 항목이라면, 바로 끝이에요!
- 중간 원소가 찾는 항목보다 크면, 그 원소와 그 뒤에 있는 모든 원소를 제거할 수 있어요.
- 중간 원소가 찾는 항목보다 작으면, 그 원소와 그 앞에 있는 모든 원소를 제거할 수 있어요.
- 배열의 모든 원소가 제거되었다면, 그 항목은 배열에 없는 거예요.
- 그렇지 않다면, 아직 제거되지 않은 배열 부분에 대해 같은 과정을 반복해요.
예를 들어볼까요?
다음과 같이 정렬된 배열에서 숫자 23을 찾는다고 해봐요: [4, 8, 12, 16, 23, 28, 32].
- 먼저 23을 중간 원소인 16과 비교해요.
- 23이 16보다 크니까, 배열의 왼쪽 절반을 제거하고
[23, 28, 32]만 남겨요.
- 그다음 23을 새로운 중간 원소인 28과 비교해요.
- 23이 28보다 작으니까, 배열의 오른쪽 절반을 제거해요:
[23].
- 찾는 항목을 발견했어요!
예외 메시지
때로는 예외를 발생시켜야 할 때가 있어요. 이럴 때는 오류의 원인이 무엇인지 알려 주는 의미 있는 오류 메시지를 항상 함께 넣어야 해요. 그러면 code를 더 읽기 쉽게 만들어 주고 debugging에도 큰 도움이 돼요. 오류의 원인이 특정 유형이라고 알고 있는 상황이라면 내장 오류 유형 중 하나를 골라 발생시켜도 되지만, 그래도 의미 있는 메시지는 꼭 포함해야 해요.
이 연습 문제에서는 주어진 값이 배열 안에서 발견되지 않을 때 raise 문으로 ValueError를 "던져야" 해요. 테스트는 exception을 raise하면서 메시지도 함께 포함해야만 통과해요.
메시지와 함께 ValueError를 발생시키려면, 메시지를 exception 유형의 인자로 작성해요.
# example when value is not found in the array.
raise ValueError("value not in array")
