Chapter 6 of 13

Updated 6 August 2026

NCERT Solutions

Searching — NCERT Solutions

Q: What are the important topics in Searching for Karnataka Board Class 12 Computer Science?

Key topics in Searching include Core Idea of Searching, Linear Search, Binary Search, Search by Hashing. Study these first, then practise questions on each for the Karnataka Board Class 12 board exam.

Q: Are these NCERT Solutions for Searching free?

The first 6 of the 11 solutions on this page are open to read. The other 5 are free with a Super Tutor account — signing up is free and needs no card.

Q: How should I revise Searching for the Karnataka Board Class 12 board exam?

Learn the core ideas first, then work through the 43 practice questions on Searching. Revise definitions regularly and use flashcards for quick recall before the exam.

Karnataka Board · Class 12 · Computer Science

NCERT Solutions for Searching, Karnataka Board Class 12 Computer Science: 11 textbook questions solved step by step.

43 questions68 flashcards3 formulas & key relations5 concepts

Interactive on Super Tutor

Studying Searching? Get the full interactive chapter.

Quizzes, flashcards, AI doubt-solver and a step-by-step study plan — built for NCERT solutions and more.

Try Super Tutor — Free

Free trial, no card needed.

An illustration showing a person searching for an item in a cluttered room, contrasting it with a person finding an item in an organized, labeled storage system, to metaphorically represent the concep — One of 9 illustrations for Searching in Super Tutor — alongside flashcards, concept maps and practice questions.

11 Questions Solved · 3 Sections

The first 6 solutions are open to read. The other 5 are free with a Super Tutor account.

Activity 6.3

6.3Consider the numList [17, 8, -4, 7, 0, 2, 19]. Sort it using the sort() function of Python's Lists. Now apply binary search to search for the key 7. Determine the number of iterations required.Show solution

Step 1 – Sort the list using sort():

Original list: $[17, 8, -4, 7, 0, 2, 19]$

After sorting: $[-4, 0, 2, 7, 8, 17, 19]$

Indices: $0, 1, 2, 3, 4, 5, 6$

Step 2 – Apply Binary Search for key = 7:

Given: $n = 7$ , $first = 0$ , $last = 6$

Iteration 1:
$mid = (0 + 6) // 2 = 3$
$numList[3] = 7 = key$

Key found at index 3 (Position 4).

Number of iterations required = 1

Since 7 happens to be the middle element of the sorted list, binary search finds it in just 1 iteration.

Activity 6.4

6.4Consider a list [-4, 0, 2, 7, 8, 17, 19]. Apply binary search to find element -4. Determine the number of key comparisons required.Show solution

Given: $numList = [-4, 0, 2, 7, 8, 17, 19]$ , $key = -4$ , $n = 7$

Initially: $first = 0$ , $last = 6$

Iteration 1:
$mid = (0 + 6) // 2 = 3$
$numList[3] = 7$
Comparison 1: $7 = -4$ ? → No
Comparison 2: $7 > -4$ ? → Yes → $last = mid - 1 = 2$

Iteration 2:
$first = 0,\ last = 2$
$mid = (0 + 2) // 2 = 1$
$numList[1] = 0$
Comparison 3: $0 = -4$ ? → No
Comparison 4: $0 > -4$ ? → Yes → $last = mid - 1 = 0$

Iteration 3:
$first = 0,\ last = 0$
$mid = (0 + 0) // 2 = 0$
$numList[0] = -4$
Comparison 5: $-4 = -4$ ? → Yes → Key found at index 0 (Position 1).

Total number of key comparisons required = 5 (across 3 iterations).

Note: In each iteration two comparisons are made (equality check and greater-than check) except the last iteration where the key is found on the equality check itself, giving $2+2+1 = 5$ comparisons.

Exercise

1Using 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.Show solution

Concept: In linear search, each element of the list is compared with the key one by one from the beginning. The position (1-based) is returned when the key is found; otherwise 'Not Found' is reported.

Given list: $[1, -2, 32, 8, 17, 19, 42, 13, 0, 44]$ (indices 0–9)

Search for key = 8:

Pass	Index (i)	numList[i]	numList[i] == 8?	Decision
1	0	1	No	Continue
2	1	-2	No	Continue
3	2	32	No	Continue
4	3	8	Yes	Found at position 4

Result: 8 is found at position 4.

Search for key = 1:

Pass	Index (i)	numList[i]	numList[i] == 1?	Decision
1	0	1	Yes	Found at position 1

Result: 1 is found at position 1.

Search for key = 99:

Pass	Index (i)	numList[i]	numList[i] == 99?	Decision
1	0	1	No	Continue
2	1	-2	No	Continue
3	2	32	No	Continue
4	3	8	No	Continue
5	4	17	No	Continue
6	5	19	No	Continue
7	6	42	No	Continue
8	7	13	No	Continue
9	8	0	No	Continue
10	9	44	No	Continue
—	End	—	—	Not Found

Result: 99 is not present in the list.

Search for key = 44:

Pass	Index (i)	numList[i]	numList[i] == 44?	Decision
1	0	1	No	Continue
2	1	-2	No	Continue
3	2	32	No	Continue
4	3	8	No	Continue
5	4	17	No	Continue
6	5	19	No	Continue
7	6	42	No	Continue
8	7	13	No	Continue
9	8	0	No	Continue
10	9	44	Yes	Found at position 10

Result: 44 is found at position 10.

Python Program:

def linearSearch(numList, key):
    for i in range(len(numList)):
        if numList[i] == key:
            return i + 1   # 1-based position
    return -1

numList = [1, -2, 32, 8, 17, 19, 42, 13, 0, 44]
for key in [8, 1, 99, 44]:
    pos = linearSearch(numList, key)
    if pos != -1:
        print(f"Key {key} found at position {pos}")
    else:
        print(f"Key {key} not found in the list")

2Use 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?Show solution

Given list: $[42, -2, 32, 8, 17, 19, 42, 13, 8, 44]$ , $key = 8$

Applying Linear Search:

Pass	Index (i)	numList[i]	numList[i] == 8?	Decision
1	0	42	No	Continue
2	1	-2	No	Continue
3	2	32	No	Continue
4	3	8	Yes	Found at position 4

Position returned = 4

Interpretation:
Linear search returns the position of the first occurrence of the key in the list. Even though 8 appears again at index 8 (position 9), the search stops as soon as the first match is found at index 3 (position 4). This means that when duplicate values are present in a list, linear search will always return the position of the first occurrence of the key and will not search further.

Python Program:

def linearSearch(numList, key):
    for i in range(len(numList)):
        if numList[i] == key:
            return i + 1
    return -1

numList = [42, -2, 32, 8, 17, 19, 42, 13, 8, 44]
key = 8
pos = linearSearch(numList, key)
if pos != -1:
    print(f"Key {key} found at position {pos}")
else:
    print(f"Key {key} not found")

Output: Key 8 found at position 4

3Write 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.Show solution

Concept: Linear search iterates through each element of the list and compares it with the key. If a match is found, the position is displayed; otherwise, a 'not found' message is printed.

Python Program:

def linearSearch(numList, key):
    """Returns 1-based position of key in numList, or -1 if not found."""
    for i in range(len(numList)):
        if numList[i] == key:
            return i + 1
    return -1

# Input: a list with a mix of negative and positive numbers
numList = [-15, 3, -7, 42, 18, -2, 9, -33, 27, 5]
print("List:", numList)

# Taking key as input from user
key = int(input("Enter the key to search: "))

pos = linearSearch(numList, key)
if pos != -1:
    print(f"Key {key} found at position {pos} in the list.")
else:
    print(f"Key {key} is not present in the list.")

Sample Runs:

Run 1: key = 42
$\text{Output: Key 42 found at position 4 in the list.}$

Run 2: key = -33
$\text{Output: Key -33 found at position 8 in the list.}$

Run 3: key = 100
$\text{Output: Key 100 is not present in the list.}$

Observation: Linear search correctly identifies the position of a key if present, and reports 'not found' otherwise. It works on both sorted and unsorted lists.

4Write 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.Show solution

Concept: Binary search works on a sorted list. It repeatedly divides the search interval in half. If the key equals the middle element, the search is successful. If the key is less than the middle element, search continues in the left half; otherwise in the right half.

Python Program:

def binarySearch(numList, key):
    """Returns 1-based position of key, or -1 if not found."""
    first = 0
    last = len(numList) - 1
    while first <= last:
        mid = (first + last) // 2
        if numList[mid] == key:
            return mid + 1          # 1-based position
        elif numList[mid] > key:
            last = mid - 1
        else:
            first = mid + 1
    return -1

# Input list of 10 integers
numList = [3, 7, 15, 22, 34, 45, 58, 67, 79, 91]
numList.sort()   # Binary search requires sorted list
print("Sorted List:", numList)

# Taking key as input
key = int(input("Enter the key to search: "))

pos = binarySearch(numList, key)
if pos != -1:
    print(f"Key {key} found at position {pos} in the list.")
else:
    print(f"Key {key} is not present in the list.")

Sample Runs:

Run 1: key = 34

$first=0, last=9, mid=4$ ; $numList[4]=34=34$ → Found at position 5

Run 2: key = 7

Iteration 1: $mid=4$ , $numList[4]=34 > 7$ → $last=3$
Iteration 2: $mid=1$ , $numList[1]=7=7$ → Found at position 2

Run 3: key = 50

Iteration 1: $mid=4$ , $34 < 50$ → $first=5$
Iteration 2: $mid=7$ , $67 > 50$ → $last=6$
Iteration 3: $mid=5$ , $45 < 50$ → $first=6$
Iteration 4: $mid=6$ , $58 > 50$ → $last=5$
$first > last$ → Not found

Observation: Binary search is significantly faster than linear search for large sorted lists.

5Following 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]. (a) Use linear search to determine the position of 1, 5, 55 and 99 in the list. Also note the number of key comparisons required. (b) Use a Python function to sort the list in ascending order. (c) Again, use linear search on the sorted list and note comparisons. (d) Use binary search on the sorted list and record iterations.

Given unsorted 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]$
(24 elements, indices 0–23)

(a) Linear Search on Unsorted List:

Key = 1:
All 24 elements are compared; 1 is not in the list.
→ Not Found, comparisons = 24

Key = 5:
Element 5 is at index 12 (position 13).
→ Found at position 13, comparisons = 13

Key = 55:
Element 55 is at index 22 (position 23).
→ Found at position 23, comparisons = 23

Key = 99:
Element 99 is at index 20 (position 21).
→ Found at position 21, comparisons = 21

(b) Sort the list using Python's sort() function:

numList = [50,31,21,28,72,41,73,93,68,43,45,78,5,17,97,71,69,61,88,75,99,44,55,9]
numList.sort()
print(numList)

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]$
(indices 0–23)

(c) Linear Search on Sorted List:

Key = 1:
All 24 elements compared; 1 is not in the list.
→ Not Found, comparisons = 24

(Note: With a sorted list, we can stop early if numList[i] > key, but standard linear search still checks all elements unless optimised.)

Key = 5:
Element 5 is at index 0 (position 1) in sorted list.
→ Found at position 1, comparisons = 1

Key = 55:
Element 55 is at index 11 (position 12) in sorted list.
→ Found at position 12, comparisons = 12

Key = 99:
Element 99 is at index 23 (position 24) in sorted list.
→ Found at position 24, comparisons = 24

(d) Binary Search on Sorted List:

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]$

Key = 1 (Not in list):

Iteration	last	mid	numList[mid]	Decision
1	23	11	55	55>1 → last=10
2	10	5	31	31>1 → last=4
3	4	2	17	17>1 → last=1
4	1	0	5	5>1 → last=-1
—	-1	—	—	first>last → Not Found

Iterations = 4

Key = 5:

Iteration	last	mid	numList[mid]	Decision
1	23	11	55	55>5 → last=10
2	10	5	31	31>5 → last=4
3	4	2	17	17>5 → last=1
4	1	0	5	5=5 → Found at position 1

Iterations = 4

Key = 55:

Iteration	first	last	mid	numList[mid]	Decision
1	0	23	11	55	55=55 → Found at position 12

Iterations = 1

Key = 99:

Iteration	first	last	mid	numList[mid]	Decision
1	0	23	11	55	55<99 → first=12
2	12	23	17	73	73<99 → first=18
3	18	23	20	88	88<99 → first=21
4	21	23	22	97	97<99 → first=23
5	23	23	23	99	99=99 → Found at position 24

Iterations = 5

Summary Table:

Key	Linear (Unsorted)	Linear (Sorted)	Binary (Sorted)
1	24 (Not Found)	24 (Not Found)	4 (Not Found)
5	13	1	4
55	23	12	1
99	21	24	5

Python Program:

def linearSearch(lst, key):
    for i in range(len(lst)):
        if lst[i] == key:
            return i + 1
    return -1

def binarySearch(lst, key):
    first, last = 0, len(lst) - 1
    iterations = 0
    while first <= last:
        mid = (first + last) // 2
        iterations += 1
        if lst[mid] == key:
            return mid + 1, iterations
        elif lst[mid] > key:
            last = mid - 1
        else:
            first = mid + 1
    return -1, iterations

numList = [50,31,21,28,72,41,73,93,68,43,45,78,5,17,97,71,69,61,88,75,99,44,55,9]
for key in [1, 5, 55, 99]:
    print(f"Linear (unsorted) for {key}:", linearSearch(numList, key))
numList.sort()
print("Sorted:", numList)
for key in [1, 5, 55, 99]:
    print(f"Linear (sorted) for {key}:", linearSearch(numList, key))
    pos, itr = binarySearch(numList, key)
    print(f"Binary search for {key}: position={pos}, iterations={itr}")

Free with a Super Tutor account

6Write 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]. (a) Use linear search to find Amazing, Perfect, Great and Wondrous. Note comparisons. (b) Sort the list. (c) Linear search on sorted list. (d) Binary search on sorted list.

Given unsorted list (16 words, indices 0–15):
$[\text{Perfect, Stupendous, Wondrous, Gorgeous, Awesome, Mirthful, Fabulous,}$
$\text{Splendid, Incredible, Outstanding, Propitious, Remarkable, Stellar, Unbelievable, Super, Amazing}]$

(a) Linear Search on Unsorted List:

Key = 'Amazing': At index 15 (position 16). Comparisons = 16

Key = 'Perfect': At index 0 (position 1). Comparisons = 1

Key = 'Great': Not in list. Comparisons = 16 (Not Found)

Key = 'Wondrous': At index 2 (position 3). Comparisons = 3

(b) Sort the list:

wordList = ['Perfect','Stupendous','Wondrous','Gorgeous','Awesome',
            'Mirthful','Fabulous','Splendid','Incredible','Outstanding',
            'Propitious','Remarkable','Stellar','Unbelievable','Super','Amazing']
wordList.sort()
print(wordList)

Sorted list (alphabetical order):
$[\text{Amazing, Awesome, Fabulous, Gorgeous, Incredible, Mirthful, Outstanding,}$
$\text{Perfect, Propitious, Remarkable, Splendid, Stellar, Stupendous, Super, Unbelievable, Wondrous}]$
(indices 0–15)

(c) Linear Search on Sorted List:

Key = 'Amazing': At index 0 (position 1). Comparisons = 1

Key = 'Perfect': At index 7 (position 8). Comparisons = 8

Key = 'Great': Not in list. Comparisons = 16 (Not Found)
(Alphabetically, 'Great' would fall between 'Gorgeous' and 'Incredible'; standard linear search checks all 16 elements.)

Key = 'Wondrous': At index 15 (position 16). Comparisons = 16

(d) Binary Search on Sorted List:

Sorted list (n=16): Amazing(0), Awesome(1), Fabulous(2), Gorgeous(3), Incredible(4), Mirthful(5), Outstanding(6), Perfect(7), Propitious(8), Remarkable(9), Splendid(10), Stellar(11), Stupendous(12), Super(13), Unbelievable(14), Wondrous(15)

Key = 'Amazing':

Iter	last	mid	wordList[mid]	Decision
1	15	7	Perfect	Perfect > Amazing → last=6
2	6	3	Gorgeous	Gorgeous > Amazing → last=2
3	2	1	Awesome	Awesome > Amazing → last=0
4	0	0	Amazing	Amazing = Amazing → Found at position 1

Iterations = 4

Key = 'Perfect':

Iter	first	last	mid	wordList[mid]	Decision
1	0	15	7	Perfect	Perfect = Perfect → Found at position 8

Iterations = 1

Key = 'Great':

Iter	first	last	mid	wordList[mid]	Decision
1	0	15	7	Perfect	Perfect > Great → last=6
2	0	6	3	Gorgeous	Gorgeous > Great → last=2
3	0	2	1	Awesome	Awesome < Great → first=2
4	2	2	2	Fabulous	Fabulous < Great → first=3
—	3	2	—	—	first>last → Not Found

Iterations = 4

Key = 'Wondrous':

Iter	first	last	mid	wordList[mid]	Decision
1	0	15	7	Perfect	Perfect < Wondrous → first=8
2	8	15	11	Stellar	Stellar < Wondrous → first=12
3	12	15	13	Super	Super < Wondrous → first=14
4	14	15	14	Unbelievable	Unbelievable < Wondrous → first=15
5	15	15	15	Wondrous	Wondrous = Wondrous → Found at position 16

Iterations = 5

Summary Table:

Key	Linear (Unsorted)	Linear (Sorted)	Binary (Sorted)
Amazing	16	1	4
Perfect	1	8	1
Great	16 (NF)	16 (NF)	4 (NF)
Wondrous	3	16	5

Python Program:

def linearSearch(lst, key):
    for i in range(len(lst)):
        if lst[i] == key:
            return i + 1
    return -1

def binarySearch(lst, key):
    first, last = 0, len(lst) - 1
    itr = 0
    while first <= last:
        mid = (first + last) // 2
        itr += 1
        if lst[mid] == key:
            return mid + 1, itr
        elif lst[mid] > key:
            last = mid - 1
        else:
            first = mid + 1
    return -1, itr

wordList = ['Perfect','Stupendous','Wondrous','Gorgeous','Awesome',
            'Mirthful','Fabulous','Splendid','Incredible','Outstanding',
            'Propitious','Remarkable','Stellar','Unbelievable','Super','Amazing']

for key in ['Amazing','Perfect','Great','Wondrous']:
    print(f"Linear (unsorted) for '{key}':", linearSearch(wordList, key))

wordList.sort()
print("Sorted list:", wordList)

for key in ['Amazing','Perfect','Great','Wondrous']:
    print(f"Linear (sorted) for '{key}':", linearSearch(wordList, key))
    pos, itr = binarySearch(wordList, key)
    print(f"Binary search for '{key}': position={pos}, iterations={itr}")

Free with a Super Tutor account

7Estimate 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 2^30 (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?

Given: Total records $n = 2^{30} = 1{,}073{,}741{,}824$ . The key is at the middle position.

Linear Search:

In linear search, elements are compared one by one from the beginning. If the key is at the middle position, we need to compare approximately half the elements before finding it.

$\text{Number of comparisons} = \frac{n}{2} = \frac{2^{30}}{2} = 2^{29} = 536{,}870{,}912$

$\approx \mathbf{536.87 \text{ million comparisons}}$

Binary Search:

In binary search, the middle element is compared first. Since the key is exactly at the middle position of the entire database:

$mid = \frac{0 + (2^{30}-1)}{2} \approx 2^{29}$

The very first comparison finds the key!

$\text{Number of comparisons (iterations)} = \mathbf{1}$

(In general, binary search requires at most $\lceil \log_2 n \rceil = \lceil \log_2 2^{30} \rceil = 30$ comparisons for any key in a database of $2^{30}$ records.)

Interpretation:

Search Method	Comparisons Required
Linear Search	$\approx 536{,}870{,}912$
Binary Search	$1$

Binary search is astronomically faster than linear search for large sorted datasets. While linear search may require over 536 million comparisons, binary search finds the same key in just 1 comparison when it is at the middle.

In the worst case, binary search needs only $\log_2(2^{30}) = 30$ comparisons to search through over a billion records, whereas linear search may need up to $2^{30}$ comparisons.

This demonstrates that binary search is highly efficient for large sorted databases, making it the preferred choice in real-world applications like searching in databases, dictionaries, and phone books.

The trade-off is that binary search requires the list to be sorted, whereas linear search works on unsorted data.

Free with a Super Tutor account

8Use 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.

Given: Collection = $[44, 121, 55, 33, 110, 77, 22, 66]$

Hash function: $h(element) = element \% 11$

Hash table size: We need slots 0 to 10 (indices 0–10).

Step 1 – Compute hash values and build the hash table:

Element	$h(element) = element \% 11$	Slot (Index)
44	$44 \% 11 = 0$	0
121	$121 \% 11 = 0$	0 ← Collision with 44!
55	$55 \% 11 = 0$	0 ← Collision!
33	$33 \% 11 = 0$	0 ← Collision!
110	$110 \% 11 = 0$	0 ← Collision!
77	$77 \% 11 = 0$	0 ← Collision!
22	$22 \% 11 = 0$	0 ← Collision!
66	$66 \% 11 = 0$	0 ← Collision!

Observation: All elements are multiples of 11, so $element \% 11 = 0$ for all. Every element maps to slot 0, causing maximum collision.

Using chaining (lists at each slot) for collision resolution:

Slot	Elements stored
0	[44, 121, 55, 33, 110, 77, 22, 66]
1	None
2	None
3	None
4	None
5	None
6	None
7	None
8	None
9	None
10	None

Step 2 – Search for 11, 44, 88, 121:

Search for 11: $h(11) = 11 \% 11 = 0$ → Check slot 0: $[44, 121, 55, 33, 110, 77, 22, 66]$ → 11 not found.

Search for 44: $h(44) = 44 \% 11 = 0$ → Check slot 0 → 44 found.

Search for 88: $h(88) = 88 \% 11 = 0$ → Check slot 0 → 88 not found.

Search for 121: $h(121) = 121 \% 11 = 0$ → Check slot 0 → 121 found.

Python Program:

# Hash table using chaining (list of lists)
HASH_SIZE = 11
hashTable = [[] for _ in range(HASH_SIZE)]

def hashFunction(element):
    return element % 11

def insert(element):
    index = hashFunction(element)
    hashTable[index].append(element)

def search(key):
    index = hashFunction(key)
    if key in hashTable[index]:
        return True
    return False

# Insert elements
collection = [44, 121, 55, 33, 110, 77, 22, 66]
for num in collection:
    insert(num)

# Display hash table
print("Hash Table:")
for i in range(HASH_SIZE):
    print(f"Slot {i}: {hashTable[i]}")

# Search
print("\nSearch Results:")
for key in [11, 44, 88, 121]:
    if search(key):
        print(f"{key} is present in the hash table.")
    else:
        print(f"{key} is NOT present in the hash table.")

Output:

Hash Table:
Slot 0: [44, 121, 55, 33, 110, 77, 22, 66]
Slot 1: []
...
Slot 10: []

Search Results:
11 is NOT present in the hash table.
44 is present in the hash table.
88 is NOT present in the hash table.
121 is present in the hash table.

Free with a Super Tutor account

9Write 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 the hash function be the length of the Country Name. Store keys and values in two separate lists at the hash index = length of country name. Search the capital of India, France and the USA in the hash table and display results.

Concept: The hash function is $h(country) = len(country)$ . The hash index (slot) is the length of the country name. Two parallel lists — one for keys (countries) and one for values (capitals) — are used. The table size must accommodate the longest country name.

Hash index computation:

Country	Length	Hash Index (slot)	Capital
UK	2	2	London
India	5	5	New Delhi
France	6	6	Paris
Australia	9	9	Canberra
Switzerland	11	11	Berne

(Note: The table in the question uses hash index = length + 1, but the standard interpretation is hash index = length of key. We follow hash index = len(country) as stated in the problem text. The table shown in the question uses 1-based indexing where index = length, which corresponds to 0-based index = length - 1. We implement as shown in the question's table for consistency.)

Following the table given in the question (hash index = length of key, 1-based, so list index = length - 1 in 0-based, but the question's table directly uses length as the list index):

We use the table as given: slot number = length of country name, and list size = 12 (to accommodate Switzerland with length 11).

Python Program:

# Hash function: length of country name
def hashFunction(country):
    return len(country)

# Table size: enough to hold longest key (Switzerland = 11 chars)
TABLE_SIZE = 12

# Two parallel lists for keys and values
keysList = [None] * TABLE_SIZE
valuesList = [None] * TABLE_SIZE

# Country-Capital dictionary
CountryCapital = {
    'India': 'New Delhi',
    'UK': 'London',
    'France': 'Paris',
    'Switzerland': 'Berne',
    'Australia': 'Canberra'
}

# Insert into hash table
for country, capital in CountryCapital.items():
    index = hashFunction(country)
    keysList[index] = country
    valuesList[index] = capital

# Display hash table
print(f"{'Hash Index':<12} {'Keys List':<15} {'Values List'}")
for i in range(TABLE_SIZE):
    print(f"{i:<12} {str(keysList[i]):<15} {str(valuesList[i])}")

# Search function
def searchCapital(country):
    index = hashFunction(country)
    if index < TABLE_SIZE and keysList[index] == country:
        return valuesList[index]
    else:
        return None

# Search for India, France, USA
print("\nSearch Results:")
for country in ['India', 'France', 'USA']:
    capital = searchCapital(country)
    if capital:
        print(f"Capital of {country} is {capital}.")
    else:
        print(f"{country} is not found in the hash table.")

Output:

Hash Index   Keys List       Values List
0            None            None
1            None            None
2            UK              London
3            None            None
4            None            None
5            India           New Delhi
6            France          Paris
7            None            None
8            None            None
9            Australia       Canberra
10           None            None
11           Switzerland     Berne

Search Results:
Capital of India is New Delhi.
Capital of France is Paris.
USA is not found in the hash table.

Explanation of Search:

India: $h(\text{'India'}) = 5$ → $keysList[5] = \text{'India'}$ → Match! → Capital = New Delhi
France: $h(\text{'France'}) = 6$ → $keysList[6] = \text{'France'}$ → Match! → Capital = Paris
USA: $h(\text{'USA'}) = 3$ → $keysList[3] = None$ → No match → Not found in hash table

Note: This hash function can cause collisions if two countries have the same name length (e.g., 'Cuba' and 'Iran' both have length 4). In such cases, only one can be stored at that slot without collision resolution. The given dataset has no such collision.

Free with a Super Tutor account

5 more solved questions in Searching

They are free with a Super Tutor account, along with practice quizzes and flashcards for this chapter. Free to start, no card needed.

Frequently Asked Questions

What are the important topics in Searching for Karnataka Board Class 12 Computer Science?

Key topics in Searching include Core Idea of Searching, Linear Search, Binary Search, Search by Hashing. Study these first, then practise questions on each for the Karnataka Board Class 12 board exam.

Are these NCERT Solutions for Searching free?

The first 6 of the 11 solutions on this page are open to read. The other 5 are free with a Super Tutor account — signing up is free and needs no card.

How should I revise Searching for the Karnataka Board Class 12 board exam?

Learn the core ideas first, then work through the 43 practice questions on Searching. Revise definitions regularly and use flashcards for quick recall before the exam.

Sources & Official References

Content is aligned to the official syllabus. Refer to the board website for the latest curriculum.

More resources for Searching

All Karnataka Board Class 12 Computer Science NCERT Solutions

For serious students

Get the full Searching chapter — start free.

Quizzes, flashcards, an AI doubt solver and a study plan for Karnataka Board Class 12 Computer Science. Free to start, no card needed.

Try Super Tutor Free

Try this chapter free

Searching — NCERT Solutions

Studying Searching? Get the full interactive chapter.

Activity 6.3

Activity 6.4

Exercise

Frequently Asked Questions

Sources & Official References

More resources for Searching

Practice Quiz

Important Questions

Revision Notes

Formula Sheet

Chapter Summary

Concept Maps

Study Plan

Flashcards

Syllabus

Get the full Searching chapter — start free.