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

Accepted Answer

To find the position of each element using linear search, we start from the first element and compare each element with the key until we find a match or reach the end of the list.

List: [1, -2, 32, 8, 17, 19, 42, 13, 0, 44]

1) Search for 8:
- Pass 1: Compare 1 with 8 → Not equal
- Pass 2: Compare -2 with 8 → Not equal
- Pass 3: Compare 32 with 8 → Not equal
- Pass 4: Compare 8 with 8 → Found at position 4

2) Search for 1:
- Pass 1: Compare 1 with 1 → Found at position 1

3) Search for 99:
- Pass 1 to 10: Compare each element with 99 → Not found
- Result: Element not present

4) Search for 44:
- Pass 1 to 9: Compare each element with 44 → Not equal
- Pass 10: Compare 44 with 44 → Found at position 10

Detailed table for searching 8 (example):
| Pass | Index | Element | Comparison with Key (8) | Decision           |
|------|-------|---------|------------------------|--------------------|
| 1    | 1     | 1       | 1 == 8? No             | Continue searching  |
| 2    | 2     | -2      | -2 == 8? No            | Continue searching  |
| 3    | 3     | 32      | 32 == 8? No            | Continue searching  |
| 4    | 4     | 8       | 8 == 8? Yes            | Element found       |

Similarly, tables can be drawn for other keys.

Positions found:
- 8 at position 4
- 1 at position 1
- 99 not found
- 44 at position 10 — Linear search checks each element sequentially until the key is found or the list ends. The position is the index where the key matches the element.

For 8, it is found at 4th index after 4 comparisons.
For 1, found immediately at 1st index.
For 99, not found after checking all elements.
For 44, found at last position (10th index).

Question 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?

Accepted Answer

Using linear search on the list [42, -2, 32, 8, 17, 19, 42, 13, 8, 44] to find key 8:

- Pass 1: 42 != 8
- Pass 2: -2 != 8
- Pass 3: 32 != 8
- Pass 4: 8 == 8 → Found at position 4

The position returned is 4.

This means that linear search returns the first occurrence of the key in the list, even if duplicates exist later in the list. — Linear search scans elements from the start and returns the index of the first match found. It does not continue searching for other occurrences once the key is found.

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

Accepted Answer

Sample Python program:

```python
# Input list of 10 numbers
numbers = list(map(int, input('Enter 10 numbers separated by space: ').split()))
key = int(input('Enter the key to search: '))

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

pos = linear_search(numbers, key)
if pos != -1:
    print(f'Key {key} found at position {pos}')
else:
    print(f'Key {key} not found in the list')

# Run for 3 different keys
for _ in range(3):
    key = int(input('Enter key to search: '))
    pos = linear_search(numbers, key)
    if pos != -1:
        print(f'Key {key} found at position {pos}')
    else:
        print(f'Key {key} not found in the list')
```

Explanation:
- The program takes a list of 10 integers (both positive and negative).
- It defines a linear search function that returns the position of the key if found, else -1.
- It searches for the key and prints the result.
- The program runs for 3 different keys as requested. — Linear search iterates through the list comparing each element with the key. If found, it returns the position; otherwise, it indicates the key is not present.

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

Accepted Answer

Sample Python program:

```python
# Input list of 10 integers
numbers = list(map(int, input('Enter 10 integers separated by space: ').split()))
# Sort the list for binary search
numbers.sort()

# Binary search function

def binary_search(lst, key):
    low = 0
    high = len(lst) - 1
    while low <= high:
        mid = (low + high) // 2
        if lst[mid] == key:
            return mid + 1  # Position (1-based)
        elif lst[mid] < key:
            low = mid + 1
        else:
            high = mid - 1
    return -1

# Run for 3 different keys
for _ in range(3):
    key = int(input('Enter key to search: '))
    pos = binary_search(numbers, key)
    if pos != -1:
        print(f'Key {key} found at position {pos}')
    else:
        print(f'Key {key} not found in the list')
```

Explanation:
- The program sorts the input list to apply binary search.
- The binary search function divides the search space by half each iteration.
- It returns the position if key is found, else -1.
- The program runs for 3 different keys as requested. — Binary search requires a sorted list. It compares the key with the middle element and reduces the search space accordingly until the key is found or search space is empty.

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

Accepted Answer

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

1) Linear search on unsorted list:
- Search 1: Not found after 24 comparisons
- Search 5: Found at position 13 after 13 comparisons
- Search 55: Found at position 23 after 23 comparisons
- Search 99: Found at position 21 after 21 comparisons

2) Sort the list in ascending order:
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]

3) Linear search on sorted list:
- Search 1: Not found after 24 comparisons
- Search 5: Found at position 1 after 1 comparison
- Search 55: Found at position 12 after 12 comparisons
- Search 99: Found at position 24 after 24 comparisons

4) Binary search on sorted list:
- Search 1:
  Iterations: 5 (mid elements checked: 50, 21, 9, 17, 9)
  Result: Not found

- Search 5:
  Iterations: 4 (mid elements checked: 50, 21, 9, 5)
  Position: 1

- Search 55:
  Iterations: 4 (mid elements checked: 50, 68, 55, 50)
  Position: 12

- Search 99:
  Iterations: 5 (mid elements checked: 50, 72, 88, 97, 99)
  Position: 24

Summary:
- Linear search comparisons vary depending on position or absence.
- Binary search iterations are logarithmic (log2 n).

Python code snippets can be used for sorting and searching to verify results. — Linear search checks elements sequentially, so the number of comparisons depends on the position of the key.
Binary search divides the search space by half each iteration, so the number of iterations is approximately log2(n).
Sorting is required for binary search.

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

Accepted Answer

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

1) Linear search on unsorted list:
- Amazing: Found at position 16 after 16 comparisons
- Perfect: Found at position 1 after 1 comparison
- Great: Not found after 16 comparisons
- Wondrous: Found at position 3 after 3 comparisons

2) Sort the list:
Sorted list = ["Amazing", "Awesome", "Fabulous", "Gorgeous", "Incredible", "Mirthful", "Outstanding", "Perfect", "Propitious", "Remarkable", "Splendid", "Stellar", "Stupendous", "Super", "Unbelievable", "Wondrous"]

3) Linear search on sorted list:
- Amazing: Found at position 1 after 1 comparison
- Perfect: Found at position 8 after 8 comparisons
- Great: Not found after 16 comparisons
- Wondrous: Found at position 16 after 16 comparisons

4) Binary search on sorted list:
- Amazing:
  Iterations: 4 (mid words checked: "Outstanding", "Fabulous", "Awesome", "Amazing")
  Position: 1

- Perfect:
  Iterations: 4 (mid words checked: "Outstanding", "Splendid", "Perfect", "Propitious")
  Position: 8

- Great:
  Iterations: 4 (mid words checked: "Outstanding", "Fabulous", "Awesome", "Incredible")
  Result: Not found

- Wondrous:
  Iterations: 4 (mid words checked: "Outstanding", "Stellar", "Unbelievable", "Wondrous")
  Position: 16

Python code can be written to automate these searches and count comparisons/iterations. — Linear search scans sequentially and counts comparisons until the word is found or list ends.
Binary search works on sorted list and reduces search space by half each iteration.
Words not present result in maximum comparisons or iterations.

Question 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?

Accepted Answer

Given:
Number of records, n = 2^30 = 1,073,741,824

1) Linear search:
- If the person is at the middle position, number of comparisons = n/2 = 2^29 = 536,870,912

2) Binary search:
- Number of comparisons = log2(n) + 1 (worst case)
- log2(2^30) = 30
- So, approximately 30 comparisons

Interpretation:
- Linear search requires about 536 million comparisons on average to find the person.
- Binary search requires only about 30 comparisons.
- Binary search is significantly more efficient for large sorted datasets.

Hence, binary search is preferred for searching in large sorted databases. — Linear search checks elements one by one, so average comparisons are half the size of the list.
Binary search divides the search space by half each time, so comparisons grow logarithmically with the number of records.

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

Accepted Answer

Hash function: h(element) = element % 11

Given elements: [44, 121, 55, 33, 110, 77, 22, 66]

Calculate hash indices:
- 44 % 11 = 0
- 121 % 11 = 0
- 55 % 11 = 0
- 33 % 11 = 0
- 110 % 11 = 0
- 77 % 11 = 0
- 22 % 11 = 0
- 66 % 11 = 0

All elements hash to index 0, so collision occurs.

Assuming chaining or linear probing is used:

Hash Table (using chaining):
Index 0: [44, 121, 55, 33, 110, 77, 22, 66]
Index 1 to 10: Empty

Search:
- 11 % 11 = 0 → Check index 0 list → 11 not found
- 44 % 11 = 0 → Check index 0 list → 44 found
- 88 % 11 = 0 → Check index 0 list → 88 not found
- 121 % 11 = 0 → Check index 0 list → 121 found

Search results:
- 11: Not found
- 44: Found
- 88: Not found
- 121: Found — All elements hash to the same index 0 causing collisions.
Using chaining, all elements are stored in a list at index 0.
Search involves checking the list at the computed index.
Elements 44 and 121 are found; 11 and 88 are not present.

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

Accepted Answer

Sample Python program:

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

# Determine max length of country names to size lists
max_len = max(len(country) for country in CountryCapital.keys())

# Initialize keys and values lists
keys_list = [None] * max_len
values_list = [None] * max_len

# Insert elements using hash function = length of country name
for country, capital in CountryCapital.items():
    index = len(country) - 1
    keys_list[index] = country
    values_list[index] = capital

print('Hash index | Country | Capital')
for i in range(max_len):
    print(f'{i} | {keys_list[i]} | {values_list[i]}')

# Search function

def search_country(country_name):
    index = len(country_name) - 1
    if index < len(keys_list) and keys_list[index] == country_name:
        return values_list[index]
    else:
        return None

# Search for capitals
for c in ['India', 'France', 'USA']:
    capital = search_country(c)
    if capital:
        print(f'Capital of {c} is {capital}')
    else:
        print(f'Capital of {c} not found in hash table')
```

Output:
- Capital of India is New Delhi
- Capital of France is Paris
- Capital of USA not found in hash table

Explanation:
- The hash function is length of the country name.
- Countries and capitals are stored at index = length - 1.
- Searching uses the same hash function and checks if the key matches.
- USA is not present, so search returns None. — The program demonstrates a simple hash table using list indices based on the length of the country name.
It stores keys and values in parallel lists.
Search uses the hash function to find the index and checks for key equality.

Question 10

What is the primary purpose of searching in computer science?

Accepted Answer

To locate a particular element in a collection of elements — Searching in computer science refers to the process of locating a particular element, called the key, within a collection of elements. It determines whether the key is present and its position if found.

Question 11

Which of the following is NOT a characteristic of Linear Search?

Accepted Answer

Requires the list to be sorted before searching — Linear search does not require the list to be sorted; it checks each element one by one until the key is found or the list ends.

Question 12

In Linear Search, what is the worst-case number of comparisons for a list of n elements?

Accepted Answer

n — In the worst case, the key is either the last element or not present at all, requiring the algorithm to compare all n elements.

Question 13

Given the list L = [2,3,9,7,-6,11,12,17,45,23,29,31,-37,41,43], how many comparisons will linear search make to find the key 12?

Accepted Answer

Linear search will make 7 comparisons to find the key 12 in the list. — Linear search compares each element starting from index 0 until it finds the key. The key 12 is at position 7 (index 6), so 7 comparisons are made.

Question 14

Explain why linear search is also called sequential search.

Accepted Answer

Linear search is called sequential search because it checks each element in the list one after another in a sequential order until the key is found or the list ends. For example, it starts from the first element and moves to the next element sequentially. — The term sequential search emphasizes the ordered, step-by-step checking of elements from start to end. This is the fundamental approach of linear search.

Question 15

In the given example, if the key 17 is the first element in the list, how many comparisons does linear search make?

Accepted Answer

1 — If the key is the first element, linear search finds it immediately after one comparison, which is the minimum number of comparisons possible.

Searching

Searching — Study Notes

6.1 INTRODUCTION

6.2 LINEAR SEARCH

6.3 BINARY SEARCH

Practice Questions — Searching

All 13 Chapters in Computer Science