Binary Search Time

Posted on 2011-04-28
Last Modified: 2012-05-11
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.
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?

    Author Comment

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

    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?

    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.

    Author Closing Comment

    Thank you for your help.

    Featured Post

    6 Surprising Benefits of Threat Intelligence

    All sorts of threat intelligence is available on the web. Intelligence you can learn from, and use to anticipate and prepare for future attacks.

    Join & Write a Comment

    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…

    730 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    15 Experts available now in Live!

    Get 1:1 Help Now