- #1
lokisapocalypse
- 32
- 0
I am working on some homework about binary searches. In case you don't know, a binary search of x items takes at most log base 2 (x) searches to find what you are looking for (assuming it is sorted data of course). Now we are asked if using a phone book as an example, we have a reference to the first name on each page, how does that change the at most number of searches.
In other words, if I have x names in the phone book with y names on z pages (x = y*z). How much is that different than log base 2 (x). Using this method it takes at most log base 2 (y) searches to find the page and then log base 2 (z) searches to find the name on that page ( log base 2 (y) + log base 2 (z) ). It seems to be the case that log base 2 (x) = log base 2 (y) + log base 2 (z). Can anyone prove this for me? Thanks.
In other words, if I have x names in the phone book with y names on z pages (x = y*z). How much is that different than log base 2 (x). Using this method it takes at most log base 2 (y) searches to find the page and then log base 2 (z) searches to find the name on that page ( log base 2 (y) + log base 2 (z) ). It seems to be the case that log base 2 (x) = log base 2 (y) + log base 2 (z). Can anyone prove this for me? Thanks.