"사전"(이차원 배열)의 이진 검색

Question

n 단어와 n/k "페이지"가 ​​있다고 가정합니다 (n/k은 자연수 임). 그래서 우리는 실제로 각 페이지가 배열이고 k 단어를 가지고있는 "페이지"의 배열 인 "사전"을 가지고 있습니다.

단어는 페이지 i의 모든 단어가 페이지 i+1의 말보다 사 전적으로 작은 방식으로 분류되어 있지만, 각 페이지에 단어를 정렬되지 않습니다.

"사전"에서 특정 단어를 찾는 방법을 작성해야합니다. 올바른 페이지를 찾기 위해 이진 검색을 사용해야한다는 것을 알고 있지만, 각 페이지의 단어가 정렬되지 않았기 때문에 그렇게 확신 할 수 없습니다.

무엇이 누락 되었습니까?

Answer 1

각 페이지의 정렬 된 첫 번째/마지막 단어가 무엇인지 모르는 경우 이진 검색은 단어가 포함될 수있는 페이지 쌍만 찾을 수 있습니다.

페이지의 "위쪽"단어가 원하는 단어 앞에 오는 경우 그 전에는 모든 페이지를 제거 할 수 있지만 은 그렇지 않습니다. 페이지; 당신의 낱말 후에 오는 페이지의 아래 더 다른 낱말이있을 수 있었다.

페이지의 맨 위 단어가 원하는 단어 뒤에 오는 경우 그 이후의 모든 페이지를 제거 할 수 있지만 은 해당되지 않습니다. 페이지; 당신의 낱말의 앞에 오는 페이지의 아래 다른 단어가있을 수 있었다.

따라서 이진 검색을 마쳤 으면 두 페이지가 남습니다. 페이지 N 상단 단어가 원하는 단어보다 작 으면 N +1 페이지의 단어가 원하는 단어보다 큽니다.

그러면 단어를 찾기 위해 두 페이지에서 선형 검색을 수행해야합니다.