Chapter 06 - Searching
6.1 Introduction
What is Searching?
Searching is the process of finding a specific element (called the key) from a collection of data.
Why Searching is Important?
- Retrieve information quickly
- Used in databases, file systems, search engines
- Improves efficiency of programs
Common Searching Techniques in CBSE
- Linear Search
- Binary Search
- Search by Hashing
6.2 Linear Search
Concept
Linear search checks each element one by one until:
- The element is found, or
- The list ends
📌 Works on sorted and unsorted lists.
Algorithm (Exam Ready)
- Start from the first element
- Compare key with each element
- If match found → success
- If end reached → failure
Example
List:
[10, 25, 30, 45, 50]
Search for 30
➡ Found at position 3
Python Program: Linear Search
def linear_search(lst, key):
for i in range(len(lst)):
if lst[i] == key:
return i
return -1
data = [10, 25, 30, 45, 50]
key = 30
pos = linear_search(data, key)
if pos != -1:
print("Element found at position", pos + 1)
else:
print("Element not found")
Characteristics
- Simple and easy
- Slow for large data
- Time complexity: O(n)
6.3 Binary Search
Concept
Binary search works on the principle:
Divide and Conquer
📌 Only works on sorted lists.
Algorithm (Exam Ready)
- Set
low = 0,high = n-1 - Find
mid = (low + high) // 2 - If
key == mid element→ found - If
key < mid element→ search left half - Else → search right half
- Repeat until found or
low > high
Example
Sorted List:
[10, 20, 30, 40, 50]
Search 30
➡ Found in fewer steps than linear search
Python Program: Binary Search (Iterative)
def binary_search(lst, key):
low = 0
high = len(lst) - 1
while low <= high:
mid = (low + high) // 2
if lst[mid] == key:
return mid
elif key < lst[mid]:
high = mid - 1
else:
low = mid + 1
return -1
data = [10, 20, 30, 40, 50]
key = 40
pos = binary_search(data, key)
if pos != -1:
print("Element found at position", pos + 1)
else:
print("Element not found")
Recursive Binary Search (Extra Knowledge)
def binary_search_rec(lst, low, high, key):
if low > high:
return -1
mid = (low + high) // 2
if lst[mid] == key:
return mid
elif key < lst[mid]:
return binary_search_rec(lst, low, mid - 1, key)
else:
return binary_search_rec(lst, mid + 1, high, key)
Characteristics
- Very fast
- Requires sorted data
- Time complexity: O(log n)
6.4 Search by Hashing
Concept
Hashing uses a hash function to convert a key into an index.
📌 The key is stored at a position calculated by the hash function.
Hash Function (Simple)
hash_index = key % table_size
Example
Table size = 10
Key = 23
Hash index = 23 % 10 = 3
Python Program: Search by Hashing
hash_table = [None] * 10
def insert(key):
index = key % 10
hash_table[index] = key
def search(key):
index = key % 10
if hash_table[index] == key:
return True
else:
return False
insert(23)
insert(45)
insert(12)
print(search(23))
print(search(99))
Collision
When two keys generate the same hash index, it is called a collision.
📌 CBSE syllabus mentions concept only, not collision handling techniques in detail.
Comparison of Searching Techniques (VERY IMPORTANT)
| Feature | Linear Search | Binary Search | Hashing |
|---|---|---|---|
| Data order | Sorted / Unsorted | Sorted only | Any |
| Speed | Slow | Fast | Very Fast |
| Complexity | O(n) | O(log n) | O(1) (avg) |
| Technique | Sequential | Divide & Conquer | Direct Access |
📝 NCERT EXAM SUMMARY (Must Memorize)
- Linear search → sequential checking
- Binary search → sorted data only
- Binary search faster than linear search
- Hashing uses hash function
- Collision occurs when two keys map to same index
- Binary search uses divide and conquer
Board-Level Solved Programs (10 Programs)
Program 1: Linear Search (Basic)
def linear_search(lst, key):
for i in range(len(lst)):
if lst[i] == key:
return i
return -1
data = [10, 25, 30, 45, 50]
key = 30
pos = linear_search(data, key)
if pos != -1:
print("Element found at position", pos + 1)
else:
print("Element not found")
Program 2: Linear Search – Count Occurrences
lst = [5, 3, 7, 3, 9, 3]
key = 3
count = 0
for item in lst:
if item == key:
count += 1
print("Occurrences of", key, ":", count)
📌 Frequently asked variation
Program 3: Linear Search in a String List
names = ["Amit", "Ravi", "Suman", "Kiran"]
key = "Suman"
found = False
for name in names:
if name == key:
found = True
break
print("Found" if found else "Not Found")
Program 4: Binary Search (Iterative)
def binary_search(lst, key):
low = 0
high = len(lst) - 1
while low <= high:
mid = (low + high) // 2
if lst[mid] == key:
return mid
elif key < lst[mid]:
high = mid - 1
else:
low = mid + 1
return -1
data = [10, 20, 30, 40, 50]
key = 40
pos = binary_search(data, key)
print("Found" if pos != -1 else "Not Found")
Program 5: Binary Search (Recursive)
def binary_search_rec(lst, low, high, key):
if low > high:
return -1
mid = (low + high) // 2
if lst[mid] == key:
return mid
elif key < lst[mid]:
return binary_search_rec(lst, low, mid - 1, key)
else:
return binary_search_rec(lst, mid + 1, high, key)
data = [5, 10, 15, 20, 25]
key = 15
pos = binary_search_rec(data, 0, len(data)-1, key)
print("Found" if pos != -1 else "Not Found")
📌 Theory + recursion
Program 6: Binary Search After Sorting
data = [45, 10, 25, 30, 5]
data.sort()
key = 25
low, high = 0, len(data)-1
found = False
while low <= high:
mid = (low + high)//2
if data[mid] == key:
found = True
break
elif key < data[mid]:
high = mid - 1
else:
low = mid + 1
print("Found" if found else "Not Found")
📌 Very common board question
Program 7: Hashing – Insert Elements
hash_table = [None] * 10
def insert(key):
index = key % 10
hash_table[index] = key
insert(12)
insert(23)
insert(45)
print(hash_table)
Program 8: Hashing – Search Element
def search(key):
index = key % 10
if hash_table[index] == key:
return True
return False
print(search(23))
print(search(99))
Program 9: Search Student Record (Linear Search)
roll = [101, 102, 103, 104]
name = ["Amit", "Ravi", "Suman", "Kiran"]
key = int(input("Enter roll number: "))
found = False
for i in range(len(roll)):
if roll[i] == key:
print("Name:", name[i])
found = True
break
if not found:
print("Record not found")
📌 Application-based
Program 10: Compare Linear vs Binary Search Steps
data = [10, 20, 30, 40, 50]
key = 50
# Linear search steps
ls_steps = 0
for item in data:
ls_steps += 1
if item == key:
break
# Binary search steps
bs_steps = 0
low, high = 0, len(data)-1
while low <= high:
bs_steps += 1
mid = (low + high)//2
if data[mid] == key:
break
elif key < data[mid]:
high = mid - 1
else:
low = mid + 1
print("Linear search steps:", ls_steps)
print("Binary search steps:", bs_steps)
📌 Conceptual + practical
Case-Study Questions (CBSE 2025 Pattern)
Case Study 1: Student Record Search
A school stores student roll numbers in a list.
Questions:
Which searching technique works on unsorted data? ✔ Linear Search
Which technique is faster on sorted data? ✔ Binary Search
Write a Python program to search a roll number.
roll = [101, 104, 102, 103] key = 102 for r in roll: if r == key: print("Record found") break else: print("Record not found")
Case Study 2: Library Book Lookup
Books are stored in sorted order.
Questions:
Which searching technique should be used? ✔ Binary Search
Why? ✔ Faster and efficient for sorted lists
Write code to search book ID.
books = [1001, 1002, 1003, 1004] key = 1003 low, high = 0, len(books)-1 while low <= high: mid = (low + high)//2 if books[mid] == key: print("Book found") break elif key < books[mid]: high = mid - 1 else: low = mid + 1
Case Study 3: Fast Lookup System Using Hashing
An application uses hashing for quick lookup.
Questions:
What is hashing? ✔ Mapping keys to indices using hash function
What is a collision? ✔ When two keys map to same index
Write a simple hashing search program.
hash_table = [None]*10 key = 27 index = key % 10 hash_table[index] = key if hash_table[index] == key: print("Key found") else: print("Key not found")