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.
Answer
list1 = [1, -2, 32, 8, 17, 19, 42, 13, 0, 44]
n = 10
1. Item = 8
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| elements | 1 | -2 | 32 | 8 | 17 | 19 | 42 | 13 | 0 | 44 |
The step-by-step process of linear search is as follows:
| index | index < n | list1[index] = key | index = index + 1 |
|---|---|---|---|
| 0 | 0 < 10 ? Yes | 1 = 8 ? No | 1 |
| 1 | 1 < 10 ? Yes | -2 = 8 ? No | 2 |
| 2 | 2 < 10 ? Yes | 32 = 8 ? No | 3 |
| 3 | 3 < 10 ? Yes | 8 = 8 ? Yes |
Therefore, for item 8, linear search returns 3 (index).
2. Item = 1
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| elements | 1 | -2 | 32 | 8 | 17 | 19 | 42 | 13 | 0 | 44 |
The step-by-step process of linear search is as follows:
| index | index < n | list1[index] = key | index = index + 1 |
|---|---|---|---|
| 0 | 0 < 10 ? Yes | 1 = 1 ? Yes |
Therefore, for item 1, linear search returns 0 (index).
3. Item = 99
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| elements | 1 | -2 | 32 | 8 | 17 | 19 | 42 | 13 | 0 | 44 |
The step-by-step process of linear search is as follows:
| index | index < n | list1[index] = key | index = index + 1 |
|---|---|---|---|
| 0 | 0 < 10 ? Yes | 1 = 99 ? No | 1 |
| 1 | 1 < 10 ? Yes | -2 = 99 ? No | 2 |
| 2 | 2 < 10 ? Yes | 32 = 99 ? No | 3 |
| 3 | 3 < 10 ? Yes | 8 = 99 ? No | 4 |
| 4 | 4 < 10 ? Yes | 17 = 99 ? No | 5 |
| 5 | 5 < 10 ? Yes | 19 = 99 ? No | 6 |
| 6 | 6 < 10 ? Yes | 42 = 99 ? No | 7 |
| 7 | 7 < 10 ? Yes | 13 = 99 ? No | 8 |
| 8 | 8 < 10 ? Yes | 0 = 99 ? No | 9 |
| 9 | 9 < 10 ? Yes | 44 = ? No | 10 |
| 10 | 10 < 10 ? No |
Since the item 99 is not found in the list, the linear search algorithm returns -1.
4. Item = 44
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| elements | 1 | -2 | 32 | 8 | 17 | 19 | 42 | 13 | 0 | 44 |
The step-by-step process of linear search is as follows:
| index | index < n | list1[index] = key | index = index + 1 |
|---|---|---|---|
| 0 | 0 < 10 ? Yes | 1 = 44 ? No | 1 |
| 1 | 1 < 10 ? Yes | -2 = 44 ? No | 2 |
| 2 | 2 < 10 ? Yes | 32 = 44 ? No | 3 |
| 3 | 3 < 10 ? Yes | 8 = 44 ? No | 4 |
| 4 | 4 < 10 ? Yes | 17 = 44 ? No | 5 |
| 5 | 5 < 10 ? Yes | 19 = 44 ? No | 6 |
| 6 | 6 < 10 ? Yes | 42 = 44 ? No | 7 |
| 7 | 7 < 10 ? Yes | 13 = 44 ? No | 8 |
| 8 | 8 < 10 ? Yes | 0 = 44 ? No | 9 |
| 9 | 9 < 10 ? Yes | 44 = 44 ? yes |
Therefore, for item 44, linear search returns 9 (index).
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?
Answer
def linear_search(lst, key):
position = -1
for i in range(len(lst)):
if lst[i] == key:
position = i
break
return position
lst = [42, -2, 32, 8, 17, 19, 42, 13, 8, 44]
key = 8
result = linear_search(lst, key)
if result != -1:
print("The position of key", key, "in the list is", result)
else:
print("Key", key, "not found in the list.")The position of key 8 in the list is 3
It will return the index 3 (position 4) for the value 8, because at this index first 8 is encountered. Simple linear search returns the index of first successful match.
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.
Answer
def lsearch(list1, key):
for k in range(0, len(list1)):
if key == list1[k]:
return k
return -1
list1 = eval(input("Enter the list: "))
for i in range(3):
item = int(input("Enter item to be searched for: "))
pos = lsearch(list1, item)
if pos == -1:
print(item, "not found")
else:
print(item, "found at index", pos)Enter the list: [32, -5, 34, 45, -6, 78, 87, 12, -9, 10]
Enter item to be searched for: -5
-5 found at index 1
Enter item to be searched for: 10
10 found at index 9
Enter item to be searched for: 100
100 not found
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.
Answer
def binarysearch(list1, key):
first = 0
last = len(list1) - 1
while first <= last:
mid = (first + last) // 2
if list1[mid] == key:
return mid
elif key < list1[mid]:
last = mid - 1
else:
first = mid + 1
return -1
list1 = eval(input("Enter the list: "))
for i in range(3):
key = int(input("Enter the key to be searched: "))
pos = binarysearch(list1, key)
if pos == -1:
print(key, "not found")
else:
print(key, "found at index", pos)Enter the list: [1, 33, 55, -77, 45, 23, -56, 23, 46, -89]
Enter the key to be searched: 33
33 found at index 1
Enter the key to be searched: 45
45 found at index 4
Enter the key to be searched: 99
99 not found
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.
Answer
1.
def linear_search(arr, key):
comparisons = 0
for k in range(len(arr)):
comparisons += 1
if key == arr[k]:
return k, comparisons
return -1, comparisons
def binary_search(arr, key):
comparisons = 0
first = 0
last = len(arr) - 1
while first <= last:
mid = (first + last) // 2
comparisons += 1
if arr[mid] == key:
return mid, comparisons
elif key < arr[mid]:
last = mid - 1
else:
first = mid + 1
return -1, comparisons
original_list = [50, 31, 21, 28, 72, 41, 73, 93, 68, 43, 45, 78, 5, 17, 97, 71, 69, 61, 88, 75, 99, 44, 55, 9]
keys = [1, 5, 55, 99]
print("Linear Search on Unsorted List:")
for key in keys:
pos, comparisons = linear_search(original_list, key)
if pos == -1:
print(key, "not found")
else:
print(key, "found at index", pos)
print("Number of comparisons:", comparisons)
original_list.sort()
print("\nSorted List:", original_list)
print("\nLinear Search on Sorted List:")
for key in keys:
pos, comparisons = linear_search(original_list, key)
if pos == -1:
print(key, "not found")
else:
print(key, "found at index", pos)
print("Number of comparisons:", comparisons)
print("\nBinary Search on Sorted List:")
for key in keys:
pos, comparisons = binary_search(original_list, key)
if pos == -1:
print(key, "not found")
else:
print(key, "found at index", pos)
print("Number of comparisons:", comparisons)Linear Search on Unsorted List:
1 not found
5 found at index 12
Number of comparisons: 13
55 found at index 22
Number of comparisons: 23
99 found at index 20
Number of comparisons: 21
Sorted List: [5, 9, 17, 21, 28, 31, 41, 43, 44, 45, 50, 55, 61, 68, 69, 71, 72, 73, 75, 78, 88, 93, 97, 99]
Linear Search on Sorted List:
1 not found
5 found at index 0
Number of comparisons: 1
55 found at index 11
Number of comparisons: 12
99 found at index 23
Number of comparisons: 24
Binary Search on Sorted List:
1 not found
5 found at index 0
Number of comparisons: 4
55 found at index 11
Number of comparisons: 1
99 found at index 23
Number of comparisons: 5
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.
Answer
def linear_search(arr, key):
comparisons = 0
for k in range(len(arr)):
comparisons += 1
if key == arr[k]:
return k, comparisons
return -1, comparisons
def binary_search(arr, key):
comparisons = 0
first = 0
last = len(arr) - 1
while first <= last:
mid = (first + last) // 2
comparisons += 1
if arr[mid] == key:
return mid, comparisons
elif key < arr[mid]:
last = mid - 1
else:
first = mid + 1
return -1, comparisons
original_list = ['Perfect', 'Stupendous', 'Wondrous',
'Gorgeous', 'Awesome', 'Mirthful', 'Fabulous', 'Splendid',
'Incredible', 'Outstanding', 'Propitious', 'Remarkable',
'Stellar', 'Unbelievable', 'Super', 'Amazing']
keys = ['Amazing', 'Perfect', 'Great', 'Wondrous']
print("Linear Search on Unsorted List:")
for key in keys:
pos, comparisons = linear_search(original_list, key)
if pos == -1:
print(key, "not found")
else:
print(key, "found at index", pos)
print("Number of comparisons:", comparisons)
original_list.sort()
print("\nSorted List:", original_list)
print("\nLinear Search on Sorted List:")
for key in keys:
pos, comparisons = linear_search(original_list, key)
if pos == -1:
print(key, "not found")
else:
print(key, "found at index", pos)
print("Number of comparisons:", comparisons)
print("\nBinary Search on Sorted List:")
for key in keys:
pos, comparisons = binary_search(original_list, key)
if pos == -1:
print(key, "not found")
else:
print(key, "found at index", pos)
print("Number of comparisons:", comparisons)Linear Search on Unsorted List:
Amazing found at index 15
Number of comparisons: 16
Perfect found at index 0
Number of comparisons: 1
Great not found
Wondrous found at index 2
Number of comparisons: 3
Sorted List: ['Amazing', 'Awesome', 'Fabulous', 'Gorgeous', 'Incredible', 'Mirthful', 'Outstanding', 'Perfect', 'Propitious', 'Remarkable', 'Splendid', 'Stellar', 'Stupendous', 'Super', 'Unbelievable', 'Wondrous']
Linear Search on Sorted List:
Amazing found at index 0
Number of comparisons: 1
Perfect found at index 7
Number of comparisons: 8
Great not found
Wondrous found at index 15
Number of comparisons: 16
Binary Search on Sorted List:
Amazing found at index 0
Number of comparisons: 4
Perfect found at index 7
Number of comparisons: 1
Great not found
Wondrous found at index 15
Number of comparisons: 5
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?
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.
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.
Answer
def h(element, hashTable):
if (hashTable[element % 10] == key):
return ((element % 10) + 1)
else:
return -1
hashTable = [None, None, None, None, None, None, None, None, None, None]
print("We have created a hashTable of 10 positions:")
print(hashTable)
L = [44, 121, 55, 33, 110, 77, 22, 66]
print("The given list is", L[::] )
for i in range(0,len(L)):
hashTable[L[i]%10] = L[i]
print("The hash table contents are: " )
for i in range(0,len(hashTable)):
print("hashindex=", i," , value =", hashTable[i])
keys = [11, 44, 88, 121]
for key in keys:
position = h(key,hashTable)
if position == -1:
print("Number",key,"is not present in the hash table")
else:
print("Number ",key," present at ",position, " position")We have created a hashTable of 10 positions:
[None, None, None, None, None, None, None, None, None, None]
The given list is [44, 121, 55, 33, 110, 77, 22, 66]
The hash table contents are:
hashindex= 0 , value = 110
hashindex= 1 , value = 121
hashindex= 2 , value = 22
hashindex= 3 , value = 33
hashindex= 4 , value = 44
hashindex= 5 , value = 55
hashindex= 6 , value = 66
hashindex= 7 , value = 77
hashindex= 8 , value = None
hashindex= 9 , value = None
Number 11 is not present in the hash table
Number 44 present at 5 position
Number 88 is not present in the hash table
Number 121 present at 2 position
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.
Answer
CountryCapital = {'India': 'New Delhi', 'UK': 'London', 'France': 'Paris',
'Switzerland': 'Berne', 'Australia': 'Canberra'}
keys = [None, None, None, None, None, None, None, None, None, None, None]
values = [None, None, None, None, None, None, None, None, None, None, None]
def calculate_hash_index(key):
return len(key) - 1
for country, capital in CountryCapital.items():
index = calculate_hash_index(country)
keys[index] = country
values[index] = capital
print("hash index = length of key - 1 | List of Keys | List of Values")
for i in range(len(keys)):
print(str(i) + "| " + str(keys[i]) + "| " + str(values[i]))
search_keys = ['India', 'France', 'USA']
print("\nSearch Results:")
for key in search_keys:
index = calculate_hash_index(key)
if keys[index] == key:
print("Capital of", key, ":", values[index])
else:
print("Capital of ", key, ": Not found")hash index = length of key - 1 | List of Keys | List of Values
0| None| None
1| UK| London
2| None| None
3| None| None
4| India| New Delhi
5| France| Paris
6| None| None
7| None| None
8| Australia| Canberra
9| None| None
10| Switzerland| Berne
Search Results:
Capital of India : New Delhi
Capital of France : Paris
Capital of USA : Not found