Advertisements
Advertisements
Question
Estimate the number of key comparisons required in binary search and linear search if we need to find the details of a person in a sorted database having 230 (1,073, 741, 824) records when details of the person being searched lie at the middle position in the database. What do you interpret from your findings?
Solution
If the record is in the middle of the sorted database, it will take one key comparison for binary search. As linear search is sequential that will take 115 keys comparison. Interpretation:
- The linear search method is useful for collecting items that are small in size and are not in any particular order.
- Binary search is a quick searching technique for large datasets which is in ascending or descending order.
APPEARS IN
RELATED QUESTIONS
Which of the following is not a limitation of binary search algorithm?
Binary search algorithm cannot be applied to ______.
Binary search makes use of ______.
When we say that in binary search with every pass the search area is reduced by half means ______.
Determine the number of comparisons required in list [-4, 0, 2,7, 8, 17, 19] to search for - 4.
A modified binary search is used when one is ______.
What is true for binary search comparisons?
For 9 elements in a list, binary search will start from element at ______.
Element in an unordered list cannot be searched using ______.
Binary search can be performed only on ordered lists.
Binary search algorithm changes the list.
Binary search works on the principle of divide and rule.
Binary list divides a list into half then sorts that half to conduct search.
Write a program that takes as input a list of 10 integers and a key value and applies binary search to find whether the key is present in the list or not. If the key is present it should display the position of the key in the list otherwise it should print an appropriate message. Run the program for at least 3 different key values and note the results.
