Why is NCERT Solution for Class 12 Chapter 6: Computer Science Searching Important?

The NCERT solution for Class 12 Chapter 6: Computer Science Searching is important as it provides a structured approach to learning, ensuring that students develop a strong understanding of foundational concepts early in their academic journey. By mastering these basics, students can build confidence and readiness for tackling more difficult concepts in their further education.

Does the NCERT Solution for Class 12 Chapter 6: Computer Science Searching help the students in preparing for the exam?

Yes, the NCERT solution for Class 12 Chapter 6: Computer Science Searching is quite useful for students in preparing for their exams. The solutions are simple, clear, and concise allowing students to understand them better. They can solve the practice questions and exercises that allow them to get exam-ready in no time.

Where Can I Get NCERT Solution for Class 12 Computer Science Chapter 6 Online?

You can get all the NCERT solutions for Class 12 Computer Science Chapter 6 from the official website of the Orchids International School. These solutions are tailored by subject matter experts and are very easy to understand.

Do I Need to Practice All Questions Provided in NCERT Solution for Class 12 Computer Science Chapter 6: Computer Science Searching ?

Yes, students must practice all the questions provided in the NCERT solution for Class 12 Computer Science Chapter 6: Computer Science Searching it will help them gain a comprehensive understanding of the concept, identify their weak areas, and strengthen their preparation.

How CBSE Students Can Utilize NCERT Solution for Class 12 Computer Science Chapter 6 Effectively?

Students can utilize the NCERT solution for Class 12 Computer Science Chapter 6 effectively by practicing the solutions regularly. Solve the exercises and practice questions given in the solution.

NCERT Solutions Class 12 Computer Science Ch 6 Searching

Question 1 :

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).

Question 2 :

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.")

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.

Question 3 :

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)

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

Question 4 :

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)

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

Question 5 :

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 :

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

Question 6 :

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)

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

Question 7 :

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 a much more efficient choice for searching compared to linear search.

Question 8 :

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")

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

Question 9 :

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")

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

NCERT Solutions for Class 12 Computer Science Chapter 6: Searching

Download PDF For NCERT Solutions for Computer-Science Searching

Access Answers to NCERT Solutions for Class 12 Computer Science Chapter 6: Searching

Exercise

Output

Output

Output

Output

Output

Output

Output