10.7 연습 문제¶
10.7.1 개념 확인¶
1. 이진 탐색은 탐색 구간을 어떻게 줄이는가¶
정렬된 배열 [2, 5, 8, 12, 16, 23, 38]에서 16을 찾는다.
양 끝을 포함하는 닫힌 구간 [i, j]를 사용하며, 중간 인덱스는
\(m=i+(j-i)/2\)다. 나눗셈 결과의 소수 부분은 버린다.
목표 값을 찾을 때까지 매 단계의 (i, j, m)과 중간 원소,
다음 단계에서 구간을 어떻게 줄이는지 적어 보자.
참고 답안
각 단계의 탐색 과정은 다음과 같다.
| 단계 | (i, j, m) |
중간 원소 | 다음 동작 |
|---|---|---|---|
| 1 | (0, 6, 3) |
12 | 12 < 16이므로 i = 4로 설정 |
| 2 | (4, 6, 5) |
23 | 23 > 16이므로 j = 4로 설정 |
| 3 | (4, 4, 4) |
16 | 목표 값을 찾았으므로 인덱스 4를 반환 |
배열이 정렬되어 있으므로 중간 값이 목표 값보다 작으면 중간 원소와 그 왼쪽을 제외할 수 있다. 중간 값이 목표 값보다 크면 중간 원소와 그 오른쪽을 제외할 수 있다.
2. 중복 원소의 왼쪽 경계와 오른쪽 경계¶
배열 [1, 2, 2, 2, 4, 6]에서 숫자 2를 찾는다.
한 학생이 이진 탐색으로 인덱스 2에서 목표 값을 찾자마자 반환한 뒤,
“인덱스 2가 숫자 2의 왼쪽 경계다.”라고 말했다.
- 이 학생의 말이 맞는가? 숫자 2의 왼쪽 경계와 오른쪽 경계는 각각 어디인지 이유와 함께 설명하라.
- 왼쪽 경계를 찾을 때 중간 원소가 목표 값과 같다면, 다음에는 어느 쪽을 계속 탐색해야 하는가?
- 오른쪽 경계를 찾을 때는 어느 쪽을 계속 탐색해야 하는가? 탐색 과정 전체를 적지 말고 방향만 설명하라.
참고 답안
-
이 학생의 말은 틀렸다. 2를 하나 찾자마자 반환하면 어떤 2를 찾았다는 것만 보장할 수 있고, 가장 왼쪽이나 가장 오른쪽의 2를 찾았다고 보장할 수는 없다. 이 문제에서 왼쪽 경계는 인덱스 1, 오른쪽 경계는 인덱스 3이다.
-
왼쪽 경계를 찾을 때는 중간 원소가 2와 같더라도 왼쪽을 계속 탐색해야 한다. 예를 들어 양 끝을 포함하는 닫힌 구간을 사용하는 경우
j = m - 1로 설정한다. -
오른쪽 경계를 찾을 때는 중간 원소가 2와 같으면 오른쪽을 계속 탐색해야 한다. 예를 들어
i = m + 1로 설정한다.
3. 데이터에 따라 어떤 탐색 방법을 선택해야 하는가¶
다음 세 상황에 알맞은 방법을 ‘선형 탐색, 이진 탐색, 해시 테이블’ 중에서 고르고 이유를 설명하라.
- 이미 정렬되어 있고 더 이상 변하지 않는 정수 \(10^7\)개에서 반복해서 값을 찾으며, 다른 자료 구조를 추가로 만들지 않는다.
- 삽입과 삭제가 빈번한 데이터 집합에서 특정 키가 있는지 반복해서 확인한다. 정렬 상태를 유지할 필요가 없고 범위 탐색도 하지 않는다.
- 정렬되지 않은 배열에서 특정 값을 한 번만 찾는다.
참고 답안
- 이진 탐색: 데이터가 정렬되어 있고 변하지 않으므로 \(O(\log n)\) 시간에 탐색할 수 있으며, 추가 공간도 필요하지 않다.
- 해시 테이블: 해시 함수가 키를 각 버킷에 비교적 고르게 분산한다면 삽입, 삭제, 키를 이용한 탐색의 평균 시간 복잡도가 모두 \(O(1)\)이다.
-
처음부터 끝까지 직접 순회: 한 번만 찾는 경우에는 정렬하거나 해시 테이블을 만드는 데에도 먼저 배열 전체를 처리해야 하므로, 이번 작업의 전체 작업량이 줄어들지 않는다.
어떤 방법을 선택할지는 데이터의 정렬 여부, 추가 자료 구조의 허용 여부, 조회 횟수, 수행해야 하는 연산에 따라 달라진다.
10.7.2 프로그래밍 연습¶
1. 정렬된 배열의 이진 탐색¶
엄격한 오름차순으로 정렬된 정수 배열 nums와 목표 값 target이 주어진다. 이진 탐색으로 target을 찾아라. 존재하면 배열 인덱스를 반환하고, 존재하지 않으면 -1을 반환하라.
풀이 힌트
- 초기 구간은 left = 0, right = n - 1이며, 구간이 비어 있지 않을 조건은 left <= right다.
- mid = left + (right - left) // 2로 중간 인덱스를 계산한다.
nums[mid]가target보다 작으면 왼쪽 경계를mid + 1로 옮긴다.nums[mid]가target보다 크면 오른쪽 경계를mid - 1로 옮긴다. 같으면 즉시 반환한다.
2. 정렬된 배열의 삽입 위치¶
엄격한 오름차순으로 정렬된 정수 배열 nums와 목표 값 target이 주어진다.
target이 이미 배열에 있으면 그 인덱스를 반환하라. 없으면 target을 삽입해도 엄격한 오름차순을 유지할 수 있는 위치를 반환하라. 답은 0일 수도 있고 배열 길이와 같을 수도 있다. 이진 탐색을 사용하라.
풀이 힌트
- 답은 0일 수도 있고 배열 길이 n일 수도 있다.
- 양 끝을 포함하는 닫힌 구간을 사용할 때
nums[mid]가target보다 크거나 같으면right = mid - 1로 설정하여 더 왼쪽의 위치를 계속 확인한다. 그렇지 않으면left = mid + 1로 설정한다. - 반복문이 끝나면 left가 삽입 위치다.