CODEWITHSUNDEEP
arraysalgorithmbinary-search
AlonAlon
AlonAlon

Reputation: 215

Binary search on a "dictionary" (two dimensional array)

Suppose we have n words and n/k "pages" (lets assume n/k is a natural number). So we have a "dictionary" which is actually an array of "pages" where each page is an array too and has k words.

The words are sorted in a way such that all the words in page i are lexicographically smaller than the words in page i+1, but the words in each page aren't sorted.

I need to write a method for finding a specific word in the "dictionary". I know I should use a binary search to find the right page, but I'm not so sure how because the words in each page aren't sorted.

what am I missing?

Upvotes: 1

Views: 357

Answers (1)

ams
ams

Reputation: 25579

If you don't know what the sorted first/last word on each page is then a binary search can only find what pair of pages may contain the word.

If the "top" word in a page comes before the word you want then you can eliminate all pages before that, but not that page; there could be another word further down the page that comes after your word.

If the top word in a page comes after the word you want, then you can eliminate all the pages after that, but not that page; there could be another word further down the page that comes before your word.

So when you finish your binary search you'll be left with two pages; page N whose top word is less than the one you want, and page N+1 whose top word is greater than the word you want.

You then have to do a linear search across both pages to find the word.

Upvotes: 2

Related Questions