Computer Science
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 lies at the middle position in the database. What do you interpret from your findings?
Python Searching
3 Likes
Answer
For binary search it will be just 1 comparison, as binary search starts with comparing the element at middle and the search will be successful with the first comparison as the desired element lies at the middle of the database.
For linear search it will be 115 comparisons, as linear search starts with comparing the first element and keeps on comparing the successive elements and thus it will take 115 comparisons to reach at the middle element, which is the desired element.
Therefore, for a sorted list, binary search is much more efficient choice for searching compared to linear search.
Answered By
1 Like
Related Questions
Following is a list of unsorted/unordered numbers:
[50, 31, 21, 28, 72, 41, 73, 93, 68, 43, 45, 78, 5, 17, 97, 71, 69, 61, 88, 75, 99, 44, 55, 9]- Use linear search to determine the position of 1, 5, 55 and 99 in the list. Also note the number of key comparisons required to find each of these numbers in the list.
- Use a Python function to sort/arrange the list in ascending order.
- Again, use linear search to determine the position of 1, 5, 55 and 99 in the list and note the number of key comparisons required to find these numbers in the list.
- Use binary search to determine the position of 1, 5, 55 and 99 in the sorted list. Record the number of iterations required in each case.
Write a program that takes as input the following unsorted list of English words:
[Perfect, Stupendous, Wondrous, Gorgeous, Awesome, Mirthful, Fabulous, Splendid, Incredible, Outstanding, Propitious, Remarkable, Stellar, Unbelievable, Super, Amazing].- Use linear search to find the position of Amazing, Perfect, Great and Wondrous in the list. Also note the number of key comparisons required to find these words in the list.
- Use a Python function to sort the list.
- Again, use linear search to determine the position of Amazing, Perfect, Great and Wondrous in the list and note the number of key comparisons required to find these words in the list.
- Use binary search to determine the position of Amazing, Perfect, Great and Wondrous in the sorted list. Record the number of iterations required in each case.
Use the hash function: h(element) = element % 10 to store the collection of numbers: [44, 121, 55, 33, 110, 77, 22, 66] in a hash table. Display the hash table created. Search if the values 11, 44, 88 and 121 are present in the hash table, and display the search results.
Write a Python program by considering a mapping of list of countries and their capital cities such as:
CountryCapital= {'India':'New Delhi','UK': 'London','France':'Paris', 'Switzerland': 'Berne', 'Australia': 'Canberra'}Let us presume that our hash function is the length of the Country Name. Take two lists of appropriate size: one for keys (Country) and one for values (Capital). To put an element in the hash table, compute its hash code by counting the number of characters in Country, then put the key and value in both the lists at the corresponding indices. For example, India has a hash code of 5. So, we store India at the 5th position (index 4) in the keys list, and New Delhi at the 5th position (index 4) in the values list and so on. So that we end up with:
hash index = length of key - 1 List of Keys List of Values 0 None None 1 UK London 2 None None 3 Cuba Havana 4 India New Delhi 5 France Paris 6 None None 7 None None 8 Australia Canberra 9 None None 10 Switzerland Berne Now search the capital of India, France and the USA in the hash table and display your result.