I'm looking at the Multiplicative Binary Search and come across this. It's the preparation you need to do for you to use the Multiplicative binary search procedure.

I somehow do not know how to do number 1. Can you explain how?

enter image description here

I thought it was getting like the formula for the binary search wherein the index = floor of((lower+upper)/2) such that instead of using floor you'll do ceiling instead.

However I came across this example, enter image description here enter image description here

enter image description here

and see that that method only worked for full binary tree but not for those who are not full but complete binary tree. Can you explain how the complete binary tree was deduced from the original table?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.