이진 탐색

지침

이번 과제는 이진 탐색 알고리즘을 구현하는 거예요.

이진 탐색 알고리즘은 배열을 절반으로 계속 나누면서, 찾고 있는 항목이 들어 있는 절반만 남기는 방식으로 항목을 찾아요. 이렇게 하면 항목을 찾을 때까지, 또는 가능한 모든 위치를 없앨 때까지 항목이 있을 수 있는 위치를 빠르게 좁혀 나갈 수 있어요.

알고리즘은 다음과 같아요:

• 정렬된 배열의 중간 원소를 찾아서, 찾고 있는 항목과 비교해요.
• 중간 원소가 찾는 항목이라면, 바로 끝이에요!
• 중간 원소가 찾는 항목보다 크면, 그 원소와 그 뒤에 있는 모든 원소를 제거할 수 있어요.
• 중간 원소가 찾는 항목보다 작으면, 그 원소와 그 앞에 있는 모든 원소를 제거할 수 있어요.
• 배열의 모든 원소가 제거되었다면, 그 항목은 배열에 없는 거예요.
• 그렇지 않다면, 아직 제거되지 않은 배열 부분에 대해 같은 과정을 반복해요.

예를 들어볼까요?

다음과 같이 정렬된 배열에서 숫자 23을 찾는다고 해봐요: [4, 8, 12, 16, 23, 28, 32].

• 먼저 23을 중간 원소인 16과 비교해요.
• 23이 16보다 크니까, 배열의 왼쪽 절반을 제거하고 [23, 28, 32]만 남겨요.
• 그다음 23을 새로운 중간 원소인 28과 비교해요.
• 23이 28보다 작으니까, 배열의 오른쪽 절반을 제거해요: [23].
• 찾는 항목을 발견했어요!

힌트

Haskell은 여러 종류의 배열을 지원해요. 이 연습 문제에서는 Data.Array의 불변이고 박싱된 비엄격 배열을 사용해요. 이 배열의 사용법에 대해서는 다음에서 더 자세히 읽어볼 수 있어요:

• A Gentle Introduction to Haskell: Arrays
• Data.Array 문서

이 연습 문제의 선택적 확장으로, 임의의 경계를 가진 배열, 예를 들어 첫 번째 인덱스가 꼭 0이 아니어도 되는 배열에서도 find 함수가 동작하도록 만들어 봐요.

---

출처

Wikipedia