Searching

This page contains the NCERT Computer Science class 12 chapter 6 Searching. You can find the solutions for the chapter 6 of NCERT class 12 Computer Science Exercise. So is the case if you are looking for NCERT class 12 Computer Science related topic Searching questions and answers for the Exercise
Buy Class 12 Computer Science Books NOW!
Exercise
Question 1
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 1
List:
[1, -2, 32, 8, 17, 19, 42, 13, 0, 44] (n = 10)
(a) Key = 8
Pass
index
index < n?
list[index]
list[index] == key?
Action
1
0
Yes
1
No
index = 1
2
1
Yes
-2
No
index = 2
3
2
Yes
32
No
index = 3
4
3
Yes
8
Yes
Found at position 4
✅ Position of 8 is 4 (Comparisons = 4). We can also say that the index of 8 is 3 (0-based indexing).
(b) Key = 1
Pass
index
index < n?
list[index]
list[index] == key?
Action
1
0
Yes
1
Yes
Found at position 1
✅ Position of 1 is 1 (Comparisons = 1). We can also say that the index of 1 is 0 (0-based indexing).
(c) Key = 99 (not present)
Pass
index
index < n?
list[index]
list[index] == key?
Action
1
0
Yes
1
No
index = 1
2
1
Yes
-2
No
index = 2
3
2
Yes
32
No
index = 3
4
3
Yes
8
No
index = 4
5
4
Yes
17
No
index = 5
6
5
Yes
19
No
index = 6
7
6
Yes
42
No
index = 7
8
7
Yes
13
No
index = 8
9
8
Yes
0
No
index = 9
10
9
Yes
44
No
index = 10
After index reaches 10 (end), search stops.
❌ 99 not found (Comparisons = 10)
(d) Key = 44
Pass
index
index < n?
list[index]
list[index] == key?
Action
1
0
Yes
1
No
index = 1
2
1
Yes
-2
No
index = 2
3
2
Yes
32
No
index = 3
4
3
Yes
8
No
index = 4
5
4
Yes
17
No
index = 5
6
5
Yes
19
No
index = 6
7
6
Yes
42
No
index = 7
8
7
Yes
13
No
index = 8
9
8
Yes
0
No
index = 9
10
9
Yes
44
Yes
Found at position 10
✅ Position of 44 is 10 (Comparisons = 10). We can also say that the index of 44 is 9 (0-based indexing).
Question 2
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 2
Linear search checks from the first element and stops at the first match.
First 8 is at index 3, so position = 3 + 1 = 4.
✅ Position returned = 4
Meaning: Linear search returns the first occurrence of the key (it does not continue to find the second 8).
Program:
def linear_search_first(arr, key):
    """
    Returns 1-based position of first occurrence, or -1 if not found.
    """
    for i in range(len(arr)):
        if arr[i] == key:
            return i + 1
    return -1


# ---- Sample run ----
num_list = [42, -2, 32, 8, 17, 19, 42, 13, 8, 44]
key = 8

pos = linear_search_first(num_list, key)

if pos == -1:
    print("Key not found")
else:
    print("Position returned:", pos)
Sample Output:
Position returned: 4
Question 3
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. 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 3
Program (Linear Search):
# Program: Linear Search on a list of 10 numbers (mix of negative and positive)

def linear_search(num_list, key):
    """
    Performs linear (sequential) search.
    Returns position (1-based) if found, else returns None.
    """
    for index in range(len(num_list)):
        # Compare each element with the key
        if num_list[index] == key:
            return index + 1  # 1-based position
    return None  # key not present


# ---- Input part ----
numbers = []
print("Enter 10 integers (negative/positive allowed):")
for i in range(10):
    n = int(input("Enter number " + str(i + 1) + ": "))
    numbers.append(n)

print("\nThe list is:", numbers)

# Keep searching until user chooses to stop
while True:
    key = int(input("\nEnter key to search: "))
    pos = linear_search(numbers, key)

    if pos is None:
        print("Search unsuccessful! Key", key, "is not present in the list.")
    else:
        print("Search successful! Key", key, "is present at position", pos)

    again = input("Search another key? (y/n): ").strip().lower()
    if again != "y":
        break
Sample Output (example run):
Enter 10 integers (negative/positive allowed):
Enter number 1: 5
Enter number 2: -2
Enter number 3: 10
Enter number 4: 7
Enter number 5: -9
Enter number 6: 12
Enter number 7: 0
Enter number 8: 4
Enter number 9: -1
Enter number 10: 8

The list is: [5, -2, 10, 7, -9, 12, 0, 4, -1, 8]

Enter key to search: 12
Search successful! Key 12 is present at position 6
Search another key? (y/n): y

Enter key to search: -1
Search successful! Key -1 is present at position 9
Search another key? (y/n): y

Enter key to search: 99
Search unsuccessful! Key 99 is not present in the list.
Search another key? (y/n): n
Question 4
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 4
Program (Binary Search):
# Program: Binary Search on a list of 10 integers

def binary_search(arr, key):
    """
    Performs binary search on a sorted list.
    Returns position (1-based) if found, else returns None.
    """
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == key:
            return mid + 1  # 1-based position
        elif arr[mid] < key:
            low = mid + 1
        else:
            high = mid - 1
    return None


# ---- Input part ----
nums = []
print("Enter 10 integers:")
for i in range(10):
    n = int(input("Enter number " + str(i + 1) + ": "))
    nums.append(n)

sorted_nums = sorted(nums)
print("\\nSorted list:", sorted_nums)

# Keep searching until user chooses to stop
while True:
    key = int(input("\\nEnter key to search: "))
    pos = binary_search(sorted_nums, key)

    if pos is None:
        print("Search unsuccessful! Key", key, "is not present in the list.")
    else:
        print("Search successful! Key", key, "is present at position", pos)

    again = input("Search another key? (y/n): ").strip().lower()
    if again != "y":
        break
Sample Output (example run):
Enter 10 integers:
Enter number 1: 7
Enter number 2: 3
Enter number 3: 10
Enter number 4: 1
Enter number 5: 4
Enter number 6: 11
Enter number 7: 5
Enter number 8: 17
Enter number 9: 21
Enter number 10: 23

Sorted list: [1, 3, 4, 5, 7, 10, 11, 17, 21, 23]

Enter key to search: 10
Search successful! Key 10 is present at position 6
Search another key? (y/n): y

Enter key to search: 2
Search unsuccessful! Key 2 is not present in the list.
Search another key? (y/n): y

Enter key to search: 23
Search successful! Key 23 is present at position 10
Search another key? (y/n): n
Question 5
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 5
A) Linear search on UNSORTED list
Key
Position (1-based)
Key Comparisons
1
Not found
24
5
13
13
55
23
23
99
21
21
Program (Linear search on unsorted list)
nums = [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]

def linear_search_with_comparisons(data, key):
    comparisons = 0
    for i in range(len(data)):
        value = data[i]
        comparisons += 1
        if value == key:
            return i + 1, comparisons
    return None, comparisons

    for k in keys:
    pos, comps = linear_search_with_comparisons(nums, k)
    if pos is None:
        print("Key", k, "Not found, Comparisons =", comps)
    else:
        print("Key", k, "Position =", pos, ", Comparisons =", comps)
Sample Output (example run):
Key 1: Not found, Comparisons = 24
Key 5: Position = 13, Comparisons = 13
Key 55: Position = 23, Comparisons = 23
Key 99: Position = 21, Comparisons = 21
B) Sorted list (ascending)
[5, 9, 17, 21, 28, 31, 41, 43, 44, 45, 50, 55, 61, 68, 69, 71, 72, 73, 75, 78, 88, 93, 97, 99]
Program (Sort using a Python function)
nums = [50, 31, 21, 28, 72, 41, 73, 93, 68, 43, 45, 78, 5, 17, 97, 71, 69, 61, 88, 75, 99, 44, 55, 9]
sorted_nums = sorted(nums)
print(sorted_nums)
Sample Output (example run):
[5, 9, 17, 21, 28, 31, 41, 43, 44, 45, 50, 55, 61, 68, 69, 71, 72, 73, 75, 78, 88, 93, 97, 99]
C) Linear search on SORTED list
Key
Position (1-based)
Key Comparisons
1
Not found
24
5
1
1
55
12
12
99
24
24
Program (Linear search on sorted list)
sorted_nums = [5, 9, 17, 21, 28, 31, 41, 43, 44, 45, 50, 55, 61, 68, 69, 71, 72, 73, 75, 78, 88, 93, 97, 99]
keys = [1, 5, 55, 99]

def linear_search_with_comparisons(data, key):
    comparisons = 0
    for i in range(len(data)):
        value = data[i]
        comparisons += 1
        if value == key:
            return i + 1, comparisons
    return None, comparisons

    for k in keys:
    pos, comps = linear_search_with_comparisons(sorted_nums, k)
    if pos is None:
        print("Key", k, "Not found, Comparisons =", comps)
    else:
        print("Key", k, "Position =", pos, ", Comparisons =", comps)
Sample Output (example run):
Key 1: Not found, Comparisons = 24
Key 5: Position = 1, Comparisons = 1
Key 55: Position = 12, Comparisons = 12
Key 99: Position = 24, Comparisons = 24
D) Binary search on SORTED list (Iterations)
Key
Position (1-based)
Iterations
1
Not found
4
5
1
4
55
12
1
99
24
5
Program (Binary search on sorted list)
sorted_nums = [5, 9, 17, 21, 28, 31, 41, 43, 44, 45, 50, 55, 61, 68, 69, 71, 72, 73, 75, 78, 88, 93, 97, 99]
keys = [1, 5, 55, 99]

def binary_search_with_iterations(data, key):
    low, high = 0, len(data) - 1
    iterations = 0
    while low <= high:
        iterations += 1
        mid = (low + high) // 2
        if data[mid] == key:
            return mid + 1, iterations
        if key < data[mid]:
            high = mid - 1
        else:
            low = mid + 1
    return None, iterations

    for k in keys:
    pos, iters = binary_search_with_iterations(sorted_nums, k)
    if pos is None:
        print("Key", k, "Not found, Iterations =", iters)
    else:
        print("Key", k, "Position =", pos, ", Iterations =", iters)
Sample Output (example run):
Key 1: Not found, Iterations = 4
Key 5: Position = 1, Iterations = 4
Key 55: Position = 12, Iterations = 1
Key 99: Position = 24, Iterations = 5
Observation: Binary search needs very few iterations because it keeps reducing the search area by half.
Question 6
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 6
A) Linear search on UNSORTED words
Key word
Position (1-based)
Comparisons
Amazing
16
16
Perfect
1
1
Great
Not found
16
Wondrous
3
3
Program (Linear search on unsorted words)
words = ['Perfect', 'Stupendous', 'Wondrous',
         'Gorgeous', 'Awesome', 'Mirthful',
         'Fabulous', 'Splendid', 'Incredible',
         'Outstanding', 'Propitious', 'Remarkable',
         'Stellar', 'Unbelievable', 'Super',
         'Amazing']
keys = ['Amazing', 'Perfect', 'Great', 'Wondrous']

def linear_search_with_comparisons(data, key):
    comparisons = 0
    for i in range(len(data)):
        value = data[i]
        comparisons += 1
        if value == key:
            return i + 1, comparisons
    return None, comparisons

for k in keys:
    pos, comps = linear_search_with_comparisons(words, k)
    if pos is None:
        print("Key", k, "Not found, Comparisons =", comps)
    else:
        print("Key", k, "Position =", pos, ", Comparisons =", comps)
Sample Output (example run):
Key Amazing: Position = 16, Comparisons = 16
Key Perfect: Position = 1, Comparisons = 1
Key Great: Not found, Comparisons = 16
Key Wondrous: Position = 3, Comparisons = 3
B) Sorted list
['Amazing', 'Awesome', 'Fabulous',
 'Gorgeous', 'Incredible', 'Mirthful',
 'Outstanding', 'Perfect', 'Propitious',
 'Remarkable', 'Splendid', 'Stellar',
 'Stupendous', 'Super', 'Unbelievable',
 'Wondrous']
Program (Sort using a Python function)
words = ['Perfect', 'Stupendous', 'Wondrous',
         'Gorgeous', 'Awesome', 'Mirthful',
         'Fabulous', 'Splendid', 'Incredible',
         'Outstanding', 'Propitious', 'Remarkable',
         'Stellar', 'Unbelievable', 'Super',
         'Amazing']
sorted_words = sorted(words)
print(sorted_words)
Sample Output (example run):
['Amazing', 'Awesome', 'Fabulous',
 'Gorgeous', 'Incredible', 'Mirthful',
 'Outstanding', 'Perfect', 'Propitious',
 'Remarkable', 'Splendid', 'Stellar',
 'Stupendous', 'Super', 'Unbelievable',
 'Wondrous']
C) Linear search on SORTED words
Key word
Position (1-based)
Comparisons
Amazing
1
1
Perfect
8
8
Great
Not found
16
Wondrous
16
16
Program (Linear search on sorted words)
sorted_words = ['Amazing', 'Awesome', 'Fabulous',
               'Gorgeous', 'Incredible', 'Mirthful',
               'Outstanding', 'Perfect', 'Propitious',
               'Remarkable', 'Splendid', 'Stellar',
               'Stupendous', 'Super', 'Unbelievable',
               'Wondrous']
keys = ['Amazing', 'Perfect', 'Great', 'Wondrous']

def linear_search_with_comparisons(data, key):
    comparisons = 0
    for i in range(len(data)):
        value = data[i]
        comparisons += 1
        if value == key:
            return i + 1, comparisons
    return None, comparisons

for k in keys:
    pos, comps = linear_search_with_comparisons(sorted_words, k)
    if pos is None:
        print("Key", k, "Not found, Comparisons =", comps)
    else:
        print("Key", k, "Position =", pos, ", Comparisons =", comps)
Sample Output (example run):
Key Amazing: Position = 1, Comparisons = 1
Key Perfect: Position = 8, Comparisons = 8
Key Great: Not found, Comparisons = 16
Key Wondrous: Position = 16, Comparisons = 16
D) Binary search on SORTED words
Key word
Position (1-based)
Iterations
Amazing
1
4
Perfect
8
1
Great
Not found
4
Wondrous
16
5
Program (Binary search on sorted words)
sorted_words = ['Amazing', 'Awesome', 'Fabulous',
               'Gorgeous', 'Incredible', 'Mirthful',
               'Outstanding', 'Perfect', 'Propitious',
               'Remarkable', 'Splendid', 'Stellar',
               'Stupendous', 'Super', 'Unbelievable',
               'Wondrous']
keys = ['Amazing', 'Perfect', 'Great', 'Wondrous']

def binary_search_with_iterations(data, key):
    low, high = 0, len(data) - 1
    iterations = 0
    while low <= high:
        iterations += 1
        mid = (low + high) // 2
        if data[mid] == key:
            return mid + 1, iterations
        if key < data[mid]:
            high = mid - 1
        else:
            low = mid + 1
    return None, iterations

for k in keys:
    pos, iters = binary_search_with_iterations(sorted_words, k)
    if pos is None:
        print("Key", k, "Not found, Iterations =", iters)
    else:
        print("Key", k, "Position =", pos, ", Iterations =", iters)
Sample Output (example run):
Key Amazing: Position = 1, Iterations = 4
Key Perfect: Position = 8, Iterations = 1
Key Great: Not found, Iterations = 4
Key Wondrous: Position = 16, Iterations = 5
Question 7
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 7
Given
N = 230 = 1,073,741,824
Key Comparisons/Iterations (middle element)
Search
How many?
Value
Binary search
Iterations
1
Linear search
Comparisons
N//2 + 1 = 229 + 1 = 536,870,913
Interpretation: Binary search is much faster on a sorted database because it halves the search space each step, while linear search does not use the order and must compare one-by-one from the start.
•
Binary search reaches the middle element in just 1 comparison.
•
With 1,073,741,824 records, linear search needs over 500 million comparisons to reach the middle.
Question 8
8. 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.
Answer 8
Here, every number is a multiple of 11, so:
•
44 % 11 = 0, 121 % 11 = 0, 55 % 11 = 0, … all give the same hash value 0
•
So, a collision happens for all items.
•
We can still store them using chaining (list at each index).
Python Program (Hashing with chaining)
# Hashing using h(x) = x % 11 with chaining (to handle collisions)

def insert_hash(table, value):
    index = value % 11
    table[index].append(value)

def search_hash(table, key):
    index = key % 11
    return key in table[index]

# Create hash table of size 11 (each slot is an empty list)
hash_table = []
for _ in range(11):
    hash_table.append([])

# Data to insert
data = [44, 121, 55, 33, 110, 77, 22, 66]

# Insert values
for v in data:
    insert_hash(hash_table, v)

# Display hash table with help text
print("Hash table (each index stores a list of values):")
for i in range(11):
    print("Hash index", i, "contains value(s):", hash_table[i])

# Search values
search_keys = [11, 44, 88, 121]
for k in search_keys:
    if search_hash(hash_table, k):
        print("Key", k, "is PRESENT in the hash table.")
    else:
        print("Key", k, "is NOT present in the hash table.")
Sample Output
Hash table (each index stores a list of values):
Hash index 0 contains value(s): [44, 121, 55, 33, 110, 77, 22, 66]
Hash index 1 contains value(s): []
Hash index 2 contains value(s): []
Hash index 3 contains value(s): []
Hash index 4 contains value(s): []
Hash index 5 contains value(s): []
Hash index 6 contains value(s): []
Hash index 7 contains value(s): []
Hash index 8 contains value(s): []
Hash index 9 contains value(s): []
Hash index 10 contains value(s): []

Key 11 is NOT present in the hash table.
Key 44 is PRESENT in the hash table.
Key 88 is NOT present in the hash table.
Key 121 is PRESENT in the hash table.
Question 9
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 9
Python Program
# Hashing based on length of country name (hash = len(country) - 1)

country_capital = {
    "India": "New Delhi",
    "UK": "London",
    "France": "Paris",
    "Switzerland": "Berne",
    "Australia": "Canberra"
}

# Maximum length here is len("Switzerland") = 11, so we need list size 11
size = 11
keys = [None] * size
values = [None] * size

# Insert into hash table
for country in country_capital:
    index = len(country) - 1
    keys[index] = country
    values[index] = country_capital[country]

# Display the hash table
print("Hash Table:")
print("Index | Key         | Value")
print("-----------------------------")
for i in range(size):
    print(i, "|", keys[i], "|", values[i])

# Search function
def get_capital(search_country):
    index = len(search_country) - 1
    if 0 <= index < size and keys[index] == search_country:
        return values[index]
    return None

# Search required countries
for c in ["India", "France", "USA"]:
    cap = get_capital(c)
    if cap is None:
        print("Capital of", c, "NOT found in hash table.")
    else:
        print("Capital of", c, "is", cap)
Sample Output
Hash Table:
Index | Key | Value
-----------------------------
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

Capital of India is New Delhi
Capital of France is Paris
Capital of USA NOT found in hash table.