Searching

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.

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

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:
```python
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")
```

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:
```python
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`

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:
```python
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.

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:
```python
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 &gt; 7 → $last=3$
- Iteration 2: $mid=1$, $numList[1]=7=7$ → Found at position 2

*Run 3:* key = 50
- Iteration 1: $mid=4$, 34 &lt; 50 → $first=5$
- Iteration 2: $mid=7$, 67 &gt; 50 → $last=6$
- Iteration 3: $mid=5$, 45 &lt; 50 → $first=6$
- Iteration 4: $mid=6$, 58 &gt; 50 → $last=5$
- first &gt; last → Not found

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

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:

```python
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 | first | last | mid | numList[mid] | Decision |
|-----------|-------|------|-----|--------------|----------|
| 1 | 0 | 23 | 11 | 55 | 55>1 → last=10 |
| 2 | 0 | 10 | 5 | 31 | 31>1 → last=4 |
| 3 | 0 | 4 | 2 | 17 | 17>1 → last=1 |
| 4 | 0 | 1 | 0 | 5 | 5>1 → last=-1 |
| — | 0 | -1 | — | — | first>last → Not Found |

Iterations = 4

Key = 5:

| Iteration | first | last | mid | numList[mid] | Decision |
|-----------|-------|------|-----|--------------|----------|
| 1 | 0 | 23 | 11 | 55 | 55>5 → last=10 |
| 2 | 0 | 10 | 5 | 31 | 31>5 → last=4 |
| 3 | 0 | 4 | 2 | 17 | 17>5 → last=1 |
| 4 | 0 | 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:
```python
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}")
```

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:

```python
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 | first | last | mid | wordList[mid] | Decision |
|------|-------|------|-----|---------------|----------|
| 1 | 0 | 15 | 7 | Perfect | Perfect > Amazing → last=6 |
| 2 | 0 | 6 | 3 | Gorgeous | Gorgeous > Amazing → last=2 |
| 3 | 0 | 2 | 1 | Awesome | Awesome > Amazing → last=0 |
| 4 | 0 | 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:
```python
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}")
```

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

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.

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

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

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

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:
```python
# 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.
```

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:
```python
# 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.