소개
수학자이면서 싱어송라이터인 사람들을 우연히 만나게 됐어요.
이들은 좋아하는 숫자마다 노래를 하나씩 써 두었는데, 짐작하겠지만 좋아하는 숫자가 아주 많아요 (0이나 73, 6174처럼요).
가장 좋아하는 숫자의 노래를 듣고 싶어졌지만, 노래가 워낙 많아서 알맞은 노래를 찾는 데는 시간이 좀 걸릴 수 있어요.
다행히 이들은 노래를 제목순으로 정렬한 재생 목록으로 정리해 두었어요. 제목은 그 노래가 다루는 숫자, 그 자체예요.
이진 탐색 알고리즘을 쓰면 제목만으로도 원하는 노래를 빠르게 찾을 수 있다는 걸 알게 돼요.
지침
이번 과제는 이진 탐색 알고리즘을 구현하는 거예요.
이진 탐색 알고리즘은 배열을 절반으로 계속 나누면서, 찾고 있는 항목이 들어 있는 절반만 남기는 방식으로 항목을 찾아요.
이렇게 하면 항목을 찾을 때까지, 또는 가능한 모든 위치를 없앨 때까지 항목이 있을 수 있는 위치를 빠르게 좁혀 나갈 수 있어요.
이진 탐색은 배열이 정렬되어 있을 때만 동작해요.
알고리즘은 다음과 같아요:
-
정렬된 배열의 중간 원소를 찾아서, 찾고 있는 항목과 비교해요.
- 중간 원소가 찾는 항목이라면, 바로 끝이에요!
- 중간 원소가 찾는 항목보다 크면, 그 원소와 그 뒤에 있는 모든 원소를 제거할 수 있어요.
- 중간 원소가 찾는 항목보다 작으면, 그 원소와 그 앞에 있는 모든 원소를 제거할 수 있어요.
- 배열의 모든 원소가 제거되었다면, 그 항목은 배열에 없는 거예요.
- 그렇지 않다면, 아직 제거되지 않은 배열 부분에 대해 같은 과정을 반복해요.
예를 들어볼까요?
다음과 같이 정렬된 배열에서 숫자 23을 찾는다고 해봐요: [4, 8, 12, 16, 23, 28, 32].
- 먼저 23을 중간 원소인 16과 비교해요.
- 23이 16보다 크니까, 배열의 왼쪽 절반을 제거하고
[23, 28, 32]만 남겨요.
- 그다음 23을 새로운 중간 원소인 28과 비교해요.
- 23이 28보다 작으니까, 배열의 오른쪽 절반을 제거해요:
[23].
- 찾는 항목을 발견했어요!
동작
풀이는 테스트 케이스에 대해 Julia에 내장된 searchsorted 함수의 동작과 일치해야 해요.
즉, 배열에서 찾은 첫 번째 일치하는 원소의 인덱스를 반환하는 대신, 하한이 배열에서 일치하는 첫 번째 원소의 인덱스이고 상한이 일치하는 마지막 원소의 인덱스인 범위를 반환해요.
다만, 풀이를 단순화하기 위해 대상 원소가 반복되지 않는다고 가정해도 돼요. 여러 개가 일치하는 경우를 다루는 보너스 과제 테스트 세트는 예외예요.
찾는 항목이 배열에 없으면, 정렬된 배열에 그 항목을 삽입할 수 있는 위치의 인덱스를 하한으로 하는 빈 범위를 반환해야 해요. 빈 범위란 상한이 하한보다 작은 범위를 말해요.
더 자세한 내용은 searchsorted 함수의 문서와 예제를 참고해요:
searchsorted(a, x; by=<transform>, lt=<comparison>, rev=false)
Return the range of indices of a which compare as equal to x (using binary
search) according to the order specified by the by, lt and rev keywords,
assuming that a is already sorted in that order.
Return an empty range located at the insertion point if a does not contain
values equal to x.
See also: insorted, searchsortedfirst, sort, findall.
Examples
julia> searchsorted([1, 2, 4, 5, 5, 7], 4) # single match
3:3
julia> searchsorted([1, 2, 4, 5, 5, 7], 5) # multiple matches
4:5
julia> searchsorted([1, 2, 4, 5, 5, 7], 3) # no match, insert in the middle
3:2
julia> searchsorted([1, 2, 4, 5, 5, 7], 9) # no match, insert at end
7:6
julia> searchsorted([1, 2, 4, 5, 5, 7], 0) # no match, insert at start
1:0
보너스 과제
- 키워드 인자
by, lt, rev를 지원하도록 풀이를 확장해 봐요. by는 배열의 모든 원소에 적용할 변환을, lt는 비교를, rev는 배열이 역순으로 정렬되어 있는지를 나타내요. 이 매개변수들을 사용할 때는 배열이 이미 이 매개변수들로 정렬되어 있다고 가정해야 해요. 자세한 내용은 sort 문서를 참고해요.
- 대상 원소가 반복되는 배열도 지원해요 (대상 원소와 같은 것으로 비교되는 첫 번째와 마지막 인덱스를 찾아요).
