§ 1이진 탐색의 원리
6. [28] (K. E. Iverson.) 연습문제 5는 나머지 구간의 길이가 신중하게 선택된 어떤 값보다 작을 때 이진 탐색에서 순차 탐색으로 전환하는 하이브리드 방법을 갖는 것이 가장 좋다는 것을 제안한다. 그러한 탐색을 위한 효율적인 MIX 프로그램을 작성하고 최적의 전환 값을 결정하라.
7. [M22] 알고리즘 U가 단계 U1을 다음과 같이 변경해도 여전히 제대로 작동할까?
a) i와 m 둘 다 floor(N/2)로 설정한 경우?
6. [28] (K. E. Iverson.) 연습문제 5는 나머지 구간의 길이가 신중하게 선택된 어떤 값보다 작을 때 이진 탐색에서 순차 탐색으로 전환하는 하이브리드 방법을 갖는 것이 가장 좋다는 것을 제안한다. 그러한 탐색을 위한 효율적인 MIX 프로그램을 작성하고 최적의 전환 값을 결정하라.
§ 2이진 탐색 트리
a) i와 m 둘 다 floor(N/2)로 설정한 경우?
b) i와 m 둘 다 ceiling(N/2)로 설정한 경우?
[힌트: 첫 번째 단계가 "i <- 0, m <- N (또는 N + 1)으로 설정하고, U4로 간다"라면?]
a) i와 m 둘 다 floor(N/2)로 설정한 경우?
§ 3이진 탐색의 정확한 구현
[힌트: 첫 번째 단계가 "i <- 0, m <- N (또는 N + 1)으로 설정하고, U4로 간다"라면?]
8. [M20] delta_j = 2^(k-j)를 (6)에서 정의된 알고리즘 C의 j번째 증분이라 하자.
b) 단계 C2에서 발생할 수 있는 i의 최솟값과 최댓값은?
[힌트: 첫 번째 단계가 "i <- 0, m <- N (또는 N + 1)으로 설정하고, U4로 간다"라면?]