NCERT Solutions for Class 12 Computer Science Chapter 6: Searching
The NCERT Solutions for Class 12 Computer Science Chapter 6 Searching describes the concepts and techniques behind various algorithms that exist for searching data. In fact, this chapter explains in detail the various searching techniques, including linear search and binary search, which a student should know to understand the basics of the design and analysis of an algorithm. The chapter also delves into the efficiency and performance of such algorithms; it revisits the time complexities of each, along with the respective situations that each method serves best. Solutions to Searching of NCERT Class 12 make these algorithms clear to the student by means of step-by-step examples and practice questions to ensure a strong foundation for further computer science studies.
Download PDF For NCERT Solutions for Computer-Science Searching
The NCERT Solutions for Class 12 Computer Science Chapter 6: Searching are tailored to help the students master the concepts that are key to success in their classrooms. The solutions given in the PDF are developed by experts and correlate with the CBSE syllabus of 2023-2024. These solutions provide thorough explanations with a step-by-step approach to solving problems. Students can easily get a hold of the subject and learn the basics with a deeper understanding. Additionally, they can practice better, be confident, and perform well in their examinations with the support of this PDF.
Download PDF
Access Answers to NCERT Solutions for Class 12 Computer Science Chapter 6: Searching
Students can access the NCERT Solutions for Class 12 Computer Science Chapter 6: Searching. Curated by experts according to the CBSE syllabus for 2023–2024, these step-by-step solutions make Computer-Science much easier to understand and learn for the students. These solutions can be used in practice by students to attain skills in solving problems, reinforce important learning objectives, and be well-prepared for tests.
Exercise
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.
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?
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.")
Output
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.
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)
Output
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.
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)
Output
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.
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)
Output
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
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.
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)
Output
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?
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 a 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.
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")
Output
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.
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")
Output
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
Admissions Open for 2025-26