Question

Database

a) Roughly describe how a binary search works. You don’t need to give pseudocode or an exact algorithm, but explain the principle or point of how it works.

b) In a binary search, does the number of operations required grow roughly exponentially or logarithmically with the number of items to be searched?       

c) Can a binary search be done on a “heap” file? Explain why or why not.

d) Explain why hashing can (usually) provide very fast lookups (retrieval) of a desired data item.

e) What is a “brute force” search of an unordered file or array?

f) On the average, how many items does a brute force linear search have to examine before finding the desired item?

g) True or false: A heap file is good (fast) for searching for desired items but slow for inserting new items.  Explain your answer.

Answer 1

Hi,

Please find the answers below:

a) Roughly describe how a binary search works.

Ans:
The requirement for binary search to work is that the array should be in a sorted in a particular order
before the search begins.
Assume that we are given with an item to be searched and an array sorted in ascending order.
You find the middle of the array and compare with the search item.

If search item is greater than the middle item in the array then search the right half of the array. If the search item is less than the middle item of the array, then search the left half of the array.

b) In a binary search, does the number of operations required grow roughly exponentially or logarithmically with the number of items to be searched?

Ans:
In a binary search, the number of operations required grow roughly logarithmically with the number of items to be searched.

O(logN) -> logarithmic of base 2

Assume searhing 16 items in an array

Next step you will search half of the array i.e 8 items
Next step you will search half of the array i.e 4 items
Next step you will search half of the array i.e 2 items.

c) Can a binary search be done on a “heap” file?

No, We can use Linear search on a heap file which is expensive. Items or records are placed in the order in which they are placed. New records are inserted at the end of the file. Sorting is an expensive operation for large files. Also, if we order the records the organization is called ordered sequential file and not heap file.

Ans:

d) Explain why hashing can (usually) provide very fast lookups (retrieval) of a desired data item.

Hashing uses a hashing function to distribute the records uniformly over the address space. This minimizes the collisions. Hash function is applied to the hash field of a record that yields the address of the disk block in which the record is stored. Hashing function makes it possible to locate a record with a given key in a single lookup.

e) What is a “brute force” search of an unordered file or array?

Brute force is a straight forward approach to solve a problem. Linear or sequential search is the brute force search
of an unordered file or array.

f) On the average, how many items does a brute force linear search have to examine before finding the desired item?
Worst case = O(n) to be searched record is in the last position of an array = you search all the records
Best case = O(1) to be searched record is the first record in the array = you are search only once.

Average case = examines half of the array for the record.

g) True or false: A heap file is good (fast) for searching for desired items but slow for inserting new items.

False. The reverse is true. Inserting new record is fast and search is slow.

Hope this helps.
Thanks.