Searching
- Using linear search determine the position of 8, 1, 99 and 44 in the list:
[1, -2, 32, 8, 17, 19, 42, 13, 0, 44]
Draw a detailed table showing the values of the variables and the decisions taken in each pass of linear search. - Use the linear search program to search the key with value 8 in the list having duplicate values such as [42, -2, 32, 8, 17, 19, 42, 13, 8, 44]. What is the position returned? What does this mean?
- Write a program that takes as input a list having a mix of 10 negative and positive numbers and a key value. Apply linear 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 keys and note the result.
- 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.
- 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.
- 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?
- Use the hash function: h(element)= element%11 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.