Help with Logarithms: Binary Searches & Phone Books

[lokisapocalypse]

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.

 

[Gokul43201]

It's not clear what you want to prove. If you sinply want to prove that, given x = yz, then log(x) = log(y) + log(z) simply recall the product rule for logarithms : log(yz) = log(y) + log(z).
...but I suspect you are asking for something else.

I'm not sure, so I'll allow you to clarify.

 

[poolwin2001]

OR that 2^(x)*2^(y)=2^(x+y)

 

[lokisapocalypse]

Actually that was all I was asking for, thanks!