Searching in Computer Science: A Complete Guide for Class 12 NCERT

What is Searching in Computer Science?

Searching is the process of finding a particular element, called the key, within a collection of data. In Class 12 NCERT Computer Science, searching is introduced as a way to locate data efficiently in lists or arrays. It is a critical operation because many computer programs depend on quickly finding information to perform tasks.

Key points about searching:

• The key is the element we want to find.
• The list or array is the collection where we search.
• Searching algorithms define how the search is performed.

Understanding searching helps in solving problems related to data retrieval, databases, and information systems.

Linear Search: The Simplest Searching Technique

Linear Search, also known as sequential search, is the most basic searching method taught in Class 12 NCERT. It works by checking each element in the list one by one from the start until the key is found or the list ends.

How Linear Search Works:

1. Start from the first element (index 0). 2. Compare the current element with the key. 3. If they match, return the position. 4. If not, move to the next element. 5. Repeat until the key is found or the list ends.

Advantages:

• Simple to implement.
• Works on unsorted or sorted lists.

Disadvantages:

• Inefficient for large lists as it may check every element.

Example:

Suppose we have the list: [8, -4, 7, 17, 0, 2, 19] and we want to find the key 17.

Steps:

• Compare 8 with 17 → No
• Compare -4 with 17 → No
• Compare 7 with 17 → No
• Compare 17 with 17 → Yes, found at index 3 (position 4)

The search stops here.

When to Use Linear Search and Its Efficiency

Linear search is best suited for:

• Small lists where performance is not critical.
• Lists that are unsorted or where sorting is not possible.
• Situations where data is dynamic and frequently changing.

Time Complexity:

• Best case: $O(1)$ when the key is the first element.
• Worst case: $O(n)$ when the key is at the last position or not present.
• Average case: $O(n/2)$ comparisons.

Space Complexity: $O(1)$ as it uses constant extra space.

Comparison Table:

This shows linear search is simple but can be slow for large datasets.

Worked Example: Finding Positions Using Linear Search

Let's apply linear search on the list [1, -2, 32, 8, 17, 19, 42, 13, 0, 44] to find the positions of keys 8, 1, 99, and 44.

For key 8, position is 4.

For key 1:

• Compare with first element 1 → Found at position 1.

For key 99:

• Check all elements → Not found, return -1.

For key 44:

• Compare elements until 10th element → Found at position 10.

This example shows how linear search returns the first occurrence if duplicates exist and returns -1 if key is absent.

Handling Duplicate Elements in Linear Search

In lists with duplicate values, linear search returns the position of the first occurrence of the key.

Example:

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

Steps:

• Compare 42 with 8 → No
• Compare -2 with 8 → No
• Compare 32 with 8 → No
• Compare 8 with 8 → Yes, found at position 4

Even though 8 appears again at position 9, linear search stops at the first match.

Implication:

• Linear search is useful when the first occurrence is sufficient.
• To find all occurrences, the search must continue through the entire list.

Tip: Modify the algorithm to record all positions if needed.

Summary and Next Steps in Searching Techniques

Linear search is the foundation of searching in Class 12 NCERT Computer Science. It is easy to understand and implement but can be inefficient for large datasets.

Key points:

• Works on any list, sorted or unsorted.
• Returns first match position.
• Time complexity can be high for large lists.

To improve efficiency, other searching techniques like Binary Search are introduced later, which require sorted lists but reduce search time significantly.

Students should practice writing linear search programs and understand its limitations before moving to advanced methods.