Solved

# Binary Search Time

Posted on 2011-04-28
537 Views
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).

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
Question by:JCW2

LVL 84

Expert Comment

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

Author Comment

Binary Search: Apply this algorithm.

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

LVL 20

Expert Comment

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

Author Comment

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

LVL 4

Accepted Solution

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

Author Closing Comment

0

## Featured Post

I use more than 1 computer in my office for various reasons. Multiple keyboards and mice take up more than just extra space, they make working a little more complicated. Using one mouse and keyboard for all of my computers makes life easier. This co…
This is about my first experience with programming Arduino.
This video teaches viewers how to encrypt an external drive that requires a password to read and edit the drive. All tasks are done in Disk Utility. Plug in the external drive you wish to encrypt: Make sure all previous data on the drive has been …
This tutorial will walk an individual through the process of installing the necessary services and then configuring a Windows Server 2012 system as an iSCSI target. To install the necessary roles, go to Server Manager, and select Add Roles and Featu…