• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 556
  • Last Modified:

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).

The problem
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.
0
JCW2
Asked:
JCW2
1 Solution
 
ozoCommented:
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?
0
 
JCW2Author Commented:
Binary Search: Apply this algorithm.

 Binary Search
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.
0
 
thehagmanCommented:
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)
0
Enhanced Intelligibility Without Cable Clutter

Challenge: The ESA office in Brussels wanted a reliable audio conference system for video conferences. Their requirement - No participant must be left out from the conference and the audio quality must not be compromised.

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

Thanks
0
 
ReclaiMeCommented:
Average block accesses = Log2(number of blocks) per search. For 30 000 records, at bfr=19 records per block, we have 1579 blocks. Log2(1579) rounded up is 11.

To read a block, assuming the file is fully fragmented (worst case scenaro) you need to wait
seek time + rotational delay time + time to transfer block

So the time would be 11 * (s+rd+btt) = 11 * (20 + 10 + 1) = 341 ms.
0
 
JCW2Author Commented:
Thank you for your help.
0

Featured Post

 The Evil-ution of Network Security Threats

What are the hacks that forever changed the security industry? To answer that question, we created an exciting new eBook that takes you on a trip through hacking history. It explores the top hacks from the 80s to 2010s, why they mattered, and how the security industry responded.

Tackle projects and never again get stuck behind a technical roadblock.
Join Now