Home › Free notes › Class 12 Computer Science › Searching

Searching – Class 12 Computer Science notes, important questions and MCQs

NCERT Class 12 Computer Science, chapter 6. Notes, key terms, important questions with answers and MCQs.

Chapter overview

Searching is the process of finding whether a given element, called the key, is present in a collection and, if so, its position. This chapter covers linear search, binary search and search by hashing. Linear search works on any list, binary search needs a sorted list but is much faster, and hashing can find an element in constant time using a hash function and hash table.

Linear and binary search

Linear (sequential) search compares the key with each element from the start until it is found or the list ends; the best case needs 1 comparison, the worst case n comparisons, so it is O(n).
Binary search works on a sorted list: compare the key with the middle element; if equal, the search ends; if smaller, search the left half; if larger, search the right half; repeat until found or the range becomes empty.
Binary search halves the search space at each step, so it takes at most about log₂n comparisons, O(log n); for 1,024 elements, at most 11 comparisons are needed.

Hashing

Hashing uses a hash function to compute the position of an element in a hash table directly, for example h(element) = element % size of table.
To search, the same hash function is applied to the key and only that position is checked, which takes constant time O(1) in the ideal case.
A collision occurs when two elements map to the same position; collision resolution techniques handle this, and a perfect hash function maps every element to a unique position.

Key terms

Searching: finding whether and where a key exists in a collection
Linear search: checking elements one by one from the beginning
Binary search: repeatedly halving a sorted list to find a key
Hash function: a function that computes the storage position of an element
Collision: two elements hashing to the same position

Important questions with answers

Why is binary search faster than linear search?2 marks

Binary search compares the key with the middle element and discards half of the remaining elements at each step, so the number of comparisons grows as log n. Linear search may need to check every element, so comparisons grow as n. However, binary search needs a sorted list.

Write a Python function for linear search.3 marks

def linear_search(L, key): for i in range(len(L)): if L[i] == key: return i; then after the loop, return -1. It returns the index of the key if found, otherwise -1.

Explain binary search with its algorithm and an example.5 marks

Binary search is an efficient method for finding a key in a sorted list. It uses three variables: low (start index), high (end index) and mid. Algorithm: set low = 0 and high = n - 1; while low <= high: compute mid = (low + high) // 2; if L[mid] == key, the key is found at mid; if L[mid] < key, the key can only be in the right half, so set low = mid + 1; otherwise, set high = mid - 1. If the loop ends without finding the key, it is not present. Python: def binary_search(L, key): low, high = 0, len(L) - 1; while low <= high: mid = (low + high) // 2; if L[mid] == key: return mid; elif L[mid] < key: low = mid + 1; else: high = mid - 1; then return -1. Example: find 23 in [5, 9, 14, 23, 31, 42, 56]. Step 1: low = 0, high = 6, mid = 3, L[3] = 23, which equals the key, so it is found in one comparison. To find 42: mid = 3, 23 < 42, so low = 4; mid = (4 + 6) // 2 = 5, L[5] = 42, found. Each comparison halves the search space, so binary search takes O(log n) time, compared with O(n) for linear search, making it very fast for large sorted lists.

Quick revision

Linear search and its complexity.
Binary search steps and complexity.
Hashing, hash table, hash function.
Collisions.

Exam tips

Binary search requires a sorted list.
Trace mid = (low + high) // 2 at each step.

Practice MCQs

Checking each element one by one from the start is
1. binary search
2. linear search
3. hashing
4. sorting
Show answer
Answer: (b) linear search. It works on unsorted lists.
Binary search can be applied only to a
1. unsorted list
2. sorted list
3. dictionary only
4. string only
Show answer
Answer: (b) sorted list. It relies on order.
Two elements mapped to the same position in a hash table is called a
1. match
2. collision
3. pass
4. swap
Show answer
Answer: (b) collision. It must be resolved.
The worst-case number of comparisons in linear search for n elements is
1. n
2. 1
3. log n
4. n/2
Show answer
Answer: (a) n. The key may be last or absent.
The time complexity of binary search is
1. O(log n)
2. O(n)
3. O(n²)
4. O(1)
Show answer
Answer: (a) O(log n). The search space halves each time.
Using h(x) = x % 10, the element 47 is stored at position
1. 7
2. 4
3. 47
4. 0
Show answer
Answer: (a) 7. 47 % 10 = 7.
In binary search on [3, 8, 12, 17, 25, 31, 40] for key 31, the first middle element checked is
1. 12
2. 17
3. 25
4. 31
Show answer
Answer: (b) 17. mid = (0 + 6) // 2 = 3, element 17.
The maximum number of comparisons binary search needs for 1,000 elements is about
1. 1000
2. 10
3. 100
4. 500
Show answer
Answer: (b) 10. 2 to the power 10 is 1,024.

All chapters of Class 12 Computer Science

Written by Kundali IQ from standard, well-established facts to help with revision. This is not an official NCERT publication; always read your textbook too.