NCERT Solutions Class 12 Computer Science Chapter 6 Searching

Linear search compares the key with each element from index 0 towards the last index, and stops at the first match. The NCERT program reports the position as index + 1, so the first element is position 1. An absent key returns None after the full scan.

• Key = 8. Compare index 0 (1), 1 (-2), 2 (32), then index 3 (8) matches. Position = 3 + 1 = 4.
• Key = 1. Compare index 0 (1), which matches at once. Position = 0 + 1 = 1.
• Key = 99. Compare every index 0 to 9; none equals 99. The search is unsuccessful.
• Key = 44. Compare every index up to index 9 (44), which matches. Position = 9 + 1 = 10.

The pass-by-pass table for key 8 shows the variable index, the test, the decision, and the update made in each pass.

def linearSearch(numList, key):
    for index in range(0, len(numList)):
        if numList[index] == key:
            return index + 1     # report 1-based position
    return None                  # key not in the list

numList = [1, -2, 32, 8, 17, 19, 42, 13, 0, 44]
for key in [8, 1, 99, 44]:
    pos = linearSearch(numList, key)
    if pos is None:
        print(key, "is not present in the list")
    else:
        print(key, "is present at position", pos)

8 is present at position 4
1 is present at position 1
99 is not present in the list
44 is present at position 10

Answer: 8 at position 4, 1 at position 1, 99 not present, 44 at position 10 (positions are 1-based, that is index + 1).

Linear search returns as soon as the first matching element is found and then stops. It does not keep scanning for more matches. So when a list holds duplicate values, it reports the position of the first occurrence only, reading from index 0.

The value 8 appears twice, at index 3 and index 8.

• Compare index 0 (42), 1 (-2), 2 (32) with 8: no match.
• Compare index 3 (8) with 8: match. The function returns at once with position 3 + 1 = 4. It never reaches the second 8 at index 8.

def linearSearch(numList, key):
    for index in range(0, len(numList)):
        if numList[index] == key:
            return index + 1     # stops at the first match
    return None

numList = [42, -2, 32, 8, 17, 19, 42, 13, 8, 44]
pos = linearSearch(numList, 8)
print("Number 8 is present at position", pos)

Number 8 is present at position 4

This means that even though 8 occurs twice (at positions 4 and 9), linear search reports only position 4, the first 8 it meets. It gives no hint that a second 8 exists further down the list.

Answer: The position returned is 4. It means linear search stops at the first occurrence of 8 (index 3, position 4) and ignores the second 8 at position 9.

Linear search scans the list element by element and compares each with the key. We first read 10 numbers with int(input()), which accepts both positive and negative values, then run the NCERT linearSearch function, which returns index + 1 on a match and None otherwise.

def linearSearch(numList, key):
    for index in range(0, len(numList)):
        if numList[index] == key:
            return index + 1
    return None

numList = []
print("Enter 10 numbers (positive or negative):")
for i in range(0, 10):
    n = int(input())
    numList.append(n)
print("The list is:", numList)

key = int(input("Enter the number to be searched: "))
pos = linearSearch(numList, key)
if pos is None:
    print("Number", key, "is not present in the list")
else:
    print("Number", key, "is present at position", pos)

The three sample runs below use the list [-7, 12, -3, 45, 8, -20, 33, -1, 17, -9].

Run 1 (key in the middle):
Enter the number to be searched: 8
Number 8 is present at position 5

Run 2 (a negative key present):
Enter the number to be searched: -20
Number -20 is present at position 6

Run 3 (key not present):
Enter the number to be searched: 100
Number 100 is not present in the list

Answer: For the list [-7, 12, -3, 45, 8, -20, 33, -1, 17, -9]: key 8 is at position 5, key -20 is at position 6, and key 100 is not present. The program reads any positive or negative number because int(input()) accepts both.

Binary search works only on a sorted list. It keeps first, last and mid = (first + last) // 2, and compares the middle element with the key. If the middle is smaller, search the right half; if larger, the left half. The search area halves each step and ends when the key is found or when first > last.

def binarySearch(numList, key):
    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:
            first = mid + 1           # search the right half
        else:
            last = mid - 1            # search the left half
    return None                       # key not found

numList = [3, 8, 15, 21, 34, 40, 56, 67, 78, 90]   # must be sorted
print("The sorted list is:", numList)
key = int(input("Enter the key to be searched: "))
pos = binarySearch(numList, key)
if pos is None:
    print(key, "is not present in the list")
else:
    print(key, "is present at position", pos)

The trace below searches for key 56 in this list, showing first, mid and last each step.

Run 1 (key present):
Enter the key to be searched: 56
56 is present at position 7

Run 2 (first element):
Enter the key to be searched: 3
3 is present at position 1

Run 3 (key not present):
Enter the key to be searched: 50
50 is not present in the list

Answer: For the sorted list [3, 8, 15, 21, 34, 40, 56, 67, 78, 90]: key 56 is at position 7 (found in 4 iterations), key 3 at position 1, and key 50 is not present. Binary search needs the list sorted first.

This question compares three things on the same data: linear search on the unsorted list, sorting with sort(), and binary search on the sorted list. A key comparison is one check of a list element against the key; an iteration of binary search is one pass of the while loop. The list has 24 elements, so indices run 0 to 23 and positions 1 to 24.

(a) Linear search on the unsorted list (one comparison per element examined):

(b) Sort the list with nums.sort() gives:

[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 the sorted list (the comparisons change because values moved):

(d) Binary search on the sorted list (count while-loop iterations):

For 55 the first middle index is (0+23)//2 = 11, and the value there is 55, so binary search finds it in a single iteration. Key 1 is smaller than every value, so the loop keeps moving last left for 4 iterations before first > last.

def linearSearchCount(numList, key):
    count = 0
    for index in range(0, len(numList)):
        count += 1
        if numList[index] == key:
            return index + 1, count
    return None, count

def binarySearchCount(numList, key):
    first, last, it = 0, len(numList) - 1, 0
    while first <= last:
        it += 1
        mid = (first + last) // 2
        if numList[mid] == key:
            return mid + 1, it
        elif numList[mid] < key:
            first = mid + 1
        else:
            last = mid - 1
    return None, it

Answer: Unsorted linear: 1 absent (24), 5 at pos 13 (13), 55 at pos 23 (23), 99 at pos 21 (21). Sorted linear: 1 absent (24), 5 at pos 1 (1), 55 at pos 12 (12), 99 at pos 24 (24). Binary on sorted: 1 absent (4), 5 at pos 1 (4), 55 at pos 12 (1), 99 at pos 24 (5). Binary needs far fewer steps than linear.

Searching and sorting work on strings just as on numbers, because Python compares words in dictionary (lexicographic) order using <, > and ==. So sort() arranges words alphabetically, which binary search needs. The list has 16 words, so indices run 0 to 15 and positions 1 to 16.

(a) Linear search on the unsorted word list:

(b) Sort the words with words.sort() gives:

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

(c) Linear search on the sorted word list:

(d) Binary search on the sorted word list:

Perfect lands on the first middle index (0+15)//2 = 7, so binary search finds it in one iteration. Great is absent, so the loop narrows over 4 iterations before first > last.

Answer: Unsorted linear: Amazing pos 16 (16), Perfect pos 1 (1), Great absent (16), Wondrous pos 3 (3). Sorted linear: Amazing pos 1 (1), Perfect pos 8 (8), Great absent (16), Wondrous pos 16 (16). Binary on sorted: Amazing pos 1 (4), Perfect pos 8 (1), Great absent (4), Wondrous pos 16 (5). Strings compare in dictionary order, so binary search works after sorting.

The number of key comparisons measures the work a search does. Linear search work depends on where the key sits, because it scans from the start. Binary search on a sorted list always checks the middle first. The total is N = 2⁷⁰ = 1,073,741,824, and the person is at the middle position.

• Linear search. To reach the middle record it must pass through every record before it. The middle is at about N / 2, so it needs roughly 1,073,741,824 ÷ 2 = 536,870,912 key comparisons, over half a billion.
• Binary search. Its first comparison is with the middle record. Since the person is at the middle, it finds the match on the first try: 1 comparison.
• Worst case for binary search. Even if the person were elsewhere, binary search would need at most log₂ N = log₂(2⁷⁰) = 30 comparisons, because each comparison halves the search area.

So binary search would never need more than 30 comparisons for this database, while linear search could need up to N (about 10⁹) in its worst case.

Answer: For the person at the middle: linear search needs about N/2 = 536,870,912 key comparisons, while binary search needs just 1. In the worst case binary search still needs at most log₂ N = 30 comparisons, versus up to N (about a billion) for linear search.

Hashing stores a value at a slot decided by a hash function. With h(element) = element % 11, the table has 11 slots, indices 0 to 10. To search, compute the key's hash index and check only that one slot. A collision happens when two different values produce the same index.

Computing the hash index of every number:

Every value is a multiple of 11, so each leaves remainder 0 and all eight fight for slot 0. This is a complete collision. With basic overwriting, the last value placed (66) survives.

def hashFind(key, hashTable):
    if hashTable[key % 11] == key:    # check just one slot
        return (key % 11) + 1
    else:
        return None

hashTable = [None] * 11               # 11 empty slots
nums = [44, 121, 55, 33, 110, 77, 22, 66]
for e in nums:
    hashTable[e % 11] = e             # place at its hash index

print("Hash table contents:")
for i in range(0, len(hashTable)):
    print("index", i, ":", hashTable[i])

for key in [11, 44, 88, 121]:
    pos = hashFind(key, hashTable)
    if pos is None:
        print(key, "is not present in the hash table")
    else:
        print(key, "is present at index", key % 11)

Hash table contents:
index 0 : 66
index 1 : None
index 2 : None
index 3 : None
index 4 : None
index 5 : None
index 6 : None
index 7 : None
index 8 : None
index 9 : None
index 10 : None
11 is not present in the hash table
44 is not present in the hash table
88 is not present in the hash table
121 is not present in the hash table

Because of the collision, slot 0 holds only 66 and slots 1 to 10 are empty. Searches for 11 and 88 (never in the list) correctly report not present, but 44 and 121 are also reported not present even though they were in the original list. The collision overwrote them.

Answer: Every number is a multiple of 11, so all hash to index 0 (a complete collision). With basic overwriting, slot 0 keeps only the last value 66 and slots 1 to 10 stay None. All four searches check slot 0, find 66, and report not present. This shows why collision handling is needed.

This is hashing with a text-based hash function: the hash index of a country is len(country) - 1. We keep two parallel lists, keys for country names and values for capitals, so the country at keys[i] has its capital at values[i]. To search, compute the key's hash index and check whether keys[index] equals the country wanted.

Computing each hash index (hash index = length of name minus 1):

def hashStore(country, capital, keys, values):
    index = len(country) - 1          # hash function
    keys[index] = country
    values[index] = capital

def hashSearch(country, keys, values):
    index = len(country) - 1
    if 0 <= index < len(keys) and keys[index] == country:
        return values[index]
    return None

size = 11
keys = [None] * size
values = [None] * size

data = {'India': 'New Delhi', 'UK': 'London', 'France': 'Paris',
        'Switzerland': 'Berne', 'Australia': 'Canberra', 'Cuba': 'Havana'}
for country, capital in data.items():
    hashStore(country, capital, keys, values)

print("Hash index | List of Keys  | List of Values")
for i in range(0, size):
    print(i, "|", keys[i], "|", values[i])

for country in ['India', 'France', 'USA']:
    capital = hashSearch(country, keys, values)
    if capital is None:
        print(country, "is not found in the hash table")
    else:
        print("Capital of", country, "is", capital)

Hash index | 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
Capital of India is New Delhi
Capital of France is Paris
USA is not found in the hash table

• India: length 5, hash index 4; keys[4] is India, so the capital is New Delhi.
• France: length 6, hash index 5; keys[5] is France, so the capital is Paris.
• USA: length 3, hash index 2; keys[2] is None, so USA is not in the table.

Answer: The table places each country at index (name length minus 1): UK at 1, Cuba at 3, India at 4, France at 5, Australia at 8, Switzerland at 10, with other slots None. Searches give: India to New Delhi, France to Paris, and USA not found.