Searching in Computer Science: Class 12 NCERT Guide

What is Searching in Computer Science?

Searching is the process of locating a particular element or value within a collection of data, such as a list or an array. In Class 12 NCERT Computer Science, searching is essential for understanding how computers retrieve information efficiently.

Key points about searching:

• It helps find whether a key (element) exists in a dataset.
• It returns the position of the key if found.
• Searching algorithms vary based on data organization.

Searching is fundamental to many applications like database queries, file systems, and internet search engines.

Linear Search: The Simplest Searching Technique

Linear search, also called sequential search, is the simplest method. It checks each element in the list one by one until it finds the key or reaches the end.

How linear search works:

1. Start from the first element. 2. Compare the current element with the key. 3. If equal, return the position. 4. Else, move to the next element. 5. Repeat until the key is found or list ends.

Example:

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

• Pass 1: 1 ≠ 8
• Pass 2: -2 ≠ 8
• Pass 3: 32 ≠ 8
• Pass 4: 8 = 8 → Found at position 4

Advantages:

• Simple to implement
• Works on unsorted data

Disadvantages:

• Inefficient for large lists (worst case: O(n) time complexity)

Linear search always returns the first occurrence if duplicates exist.

Binary Search: Efficient Searching on Sorted Lists

Binary search works only on sorted lists. It repeatedly divides the search interval in half to quickly locate the key.

Steps:

1. Find the middle element. 2. If middle element equals key, return position. 3. If key is less, repeat search on left half. 4. If key is greater, repeat on right half. 5. Continue until key is found or interval is empty.

Formula for middle index:

$$ mid = \left\lfloor \frac{low + high}{2} \right\rfloor $$

Example:

Sorted list: [2, 8, 15, 23, 38, 56, 72] Search key: 23

• low=0, high=6, mid=3 → element=23 → Found at position 4

Advantages:

• Much faster than linear search (O(log n) time complexity)

Disadvantages:

• Requires sorted data
• More complex to implement than linear search

Hashing: Constant Time Searching Using Hash Functions

Hashing is a powerful searching technique taught in Class 12 NCERT Computer Science that allows locating elements in constant time, ideally with just one comparison.

Key concepts:

• A hash function computes an index from the element's value.
• The index points to the position in a hash table where the element is stored.

Example of hash function (remainder method):

$$ hash\_value = element \% table\_size $$

Consider inserting elements: 34, 16, 2, 93, 80, 77, 51 into a hash table of size 10.

The hash table stores elements at these indices:

Collision: When two elements produce the same hash value, it is called a collision. Collision resolution techniques like chaining or open addressing handle this.

Advantages:

• Very fast search (average O(1) time)
• Useful in databases, caching, and associative arrays

Disadvantages:

• Requires good hash functions
• Handling collisions adds complexity

Comparing Searching Techniques: When to Use What?

Choosing the right searching technique depends on the data and requirements. Here's a comparison:

Summary:

• Use linear search for small or unsorted lists.
• Use binary search for large, sorted lists.
• Use hashing for very fast search in large datasets where extra memory is available.

Worked Example: Searching for a Key Using Linear Search

Let's apply linear search to find the position of key 8 in the list:

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

The search stops at the first occurrence of 8, returning position 4.

This example shows linear search's step-by-step comparison process.

Summary and Exam Tips for Searching in Class 12 NCERT

To excel in the Searching chapter:

• Understand the working of linear, binary, and hashing search.
• Practice writing and tracing simple search algorithms.
• Remember the conditions for using binary search (sorted data).
• Learn the hashing concept, hash functions, and collision handling.
• Solve NCERT exercises and sample problems thoroughly.

Searching is a common exam topic with questions on algorithm steps, comparisons, and coding. Focus on clarity and logic in your answers.