Link to home
Start Free TrialLog in
Avatar of JCW2
JCW2

asked on

Binary Search Time

Note: I'm not looking for a direct answer.

In this problem, I'm trying to understand how to find the time needed for the binary search (part g). The number of block accesses apparently is log_2(b).

User generated image
g.) Assume that the records are ordered via some key field. Calculate the average number of block accesses and the average time needed to search for an arbitrary record in the file, using binary search.
Avatar of ozo
ozo
Flag of United States of America image

What are you having trouble with?
Do you know what a binary search is?
Do you know the average number of accesses for a binary search?
Do you know how to find the average time needed to do an access?
Avatar of JCW2
JCW2

ASKER

Binary Search: Apply this algorithm.

 User generated image
Average number of accesses: log_2(b), the 2 being a subscript; the b being the number of blocks.

The average time needed to do an access: No; that's what I'm confused about.
Each access involves seeking and reading a new block, which costs time as given in the description.
Actually, this does not hold for the last few steps as the block in question may alrdy have been read (you may want to keep two or three blocks in memory for this)
Avatar of JCW2

ASKER

Okay, thanks. What I was looking for was a formula, a way to derive a formula, or a link. Is this reasonably possible?

Thanks
ASKER CERTIFIED SOLUTION
Avatar of ReclaiMe
ReclaiMe
Flag of United States of America image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Avatar of JCW2

ASKER

Thank you for your help.