Searching — NCERT Solutions

Given list:
$[Perfect, Stupendous, Wondrous, Gorgeous, Awesome, Mirthful, Fabulous, Splendid, Incredible, Outstanding, Propitious, Remarkable, Stellar, Unbelievable, Super, Amazing]$

Python program

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

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

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

keys = ["Amazing", "Perfect", "Great", "Wondrous"]

print("Linear search in original list:")
for key in keys:
    pos, comps = linearSearch(words, key)
    print(key, pos, comps)

sorted_words = sorted(words)
print("Sorted list:", sorted_words)

print("Linear search in sorted list:")
for key in keys:
    pos, comps = linearSearch(sorted_words, key)
    print(key, pos, comps)

print("Binary search in sorted list:")
for key in keys:
    pos, iters = binarySearch(sorted_words, key)
    print(key, pos, iters)

Results

Linear search in original list

• Amazing → position 16, comparisons 16
• Perfect → position 1, comparisons 1
• Great → not found, comparisons 16
• Wondrous → position 3, comparisons 3

Sorted list

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

Linear search in sorted list

• Amazing → position 1, comparisons 1
• Perfect → position 8, comparisons 8
• Great → not found, comparisons 16
• Wondrous → position 16, comparisons 16

Binary search in sorted list

• Amazing → position 1, iterations 4
• Perfect → position 8, iterations 1
• Great → not found, iterations 4
• Wondrous → position 16, iterations 5

The database has $2^{30} = 1,073,741,824$ records.

Binary search

Binary search compares by halving the search area each time.
To find the middle element of a list with $2^{30}$ records, it needs only 1 comparison/iteration.

Linear search

Linear search checks elements one by one.
If the required record lies in the middle position, then it will need
$$\frac{2^{30}}{2} = 2^{29} = 536,870,912$$
comparisons.

Interpretation

Binary search is vastly more efficient than linear search for a large sorted database. It reduces the search area by half each time, while linear search may need to check a huge number of records.

Using the hash function
$$h(\text{element}) = \text{element} \% 11$$
for the list $[44, 121, 55, 33, 110, 77, 22, 66]$:

• $44 \% 11 = 0$
• $121 \% 11 = 0$
• $55 \% 11 = 0$
• $33 \% 11 = 0$
• $110 \% 11 = 0$
• $77 \% 11 = 0$
• $22 \% 11 = 0$
• $66 \% 11 = 0$

So all values map to the same position, which means collision occurs repeatedly.

Hash table created

Since the chapter says collision resolution is beyond scope, we can only say that this hash function is not suitable for this set of numbers because all of them produce remainder 0.

Searching

For any key, the hash index is $key \% 11$.

• 11 → $11 \% 11 = 0$ → table position 0 contains a colliding value, so presence cannot be confirmed without collision handling.
• 44 → $44 \% 11 = 0$ → same issue
• 88 → $88 \% 11 = 0$ → same issue
• 121 → $121 \% 11 = 0$ → same issue

Conclusion

This example shows a case of collision. A perfect hash function is not available here, because several elements map to the same slot.

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

# create lists large enough for indices up to length 11
keys = [None] * 11
values = [None] * 11

# store key-value pairs using length of country name - 1 as index
for country, capital in CountryCapital.items():
    index = len(country) - 1
    keys[index] = country
    values[index] = capital

print("Keys list:", keys)
print("Values list:", values)

def searchCapital(country):
    index = len(country) - 1
    if keys[index] == country:
        return values[index]
    return None

for c in ['India', 'France', 'USA']:
    result = searchCapital(c)
    if result is None:
        print(c, 'is not present in the hash table')
    else:
        print('Capital of', c, 'is', result)

Expected result

• India → New Delhi
• France → Paris
• USA → not present in the hash table

This uses the length of the country name as the hash code, exactly as described in the chapter.