Searching is one of the most fundamental operations performed in data structures. It is the process of locating a desired element or record from a data collection based on a specific criterion, usually a key value. This chapter dives deep into the concept of searching, exploring different search algorithms, their efficiencies, and practical applications for real-time systems. Mastering searching operations is essential for B.Tech and BCA students as it lays the foundation for understanding more complex operations such as sorting, indexing, and hashing.
Definition of Searching
Searching refers to the process of finding the location of a given element in a data structure such as an array, linked list, tree, or graph. The goal is either to confirm the presence of the element or retrieve its position/index.
Types of Search Operations
- Linear Search (Sequential Search)
- Binary Search
- Ternary Search
- Jump Search
- Exponential Search
- Fibonacci Search
- Hashing (as a search technique)
- Search in Linked Lists
- Search in Trees
- Search in Graphs
1. Linear Search
Linear Search is the simplest method used to search for an element in a data structure.
Working: Each element is checked one by one until the desired element is found or the list ends.
Algorithm:
cppCopyEditfor i from 0 to n-1:
if arr[i] == key:
return i
return -1
Time Complexity:
- Best Case: O(1) (element found at first position)
- Average Case: O(n)
- Worst Case: O(n)
Space Complexity: O(1)
📌 Insert Diagram: Flowchart of Linear Search Algorithm
2. Binary Search
Binary Search is a more efficient technique than linear search, applicable only on sorted arrays.
Working:
- Compare the target with the middle element.
- If they are equal, return the index.
- If the target is smaller, repeat the search in the left sub-array.
- If the target is greater, search in the right sub-array.
Algorithm:
cppCopyEditstart = 0
end = n - 1
while start <= end:
mid = (start + end) / 2
if arr[mid] == key:
return mid
else if arr[mid] < key:
start = mid + 1
else:
end = mid - 1
return -1
Time Complexity:
- Best Case: O(1)
- Average/Worst Case: O(log n)
Space Complexity:
- Iterative: O(1)
- Recursive: O(log n) due to stack
📌 Insert Diagram: Binary Search Tree Traversal Showing Midpoint Reduction
3. Ternary Search
Ternary Search is a divide-and-conquer search similar to binary search but divides the array into three parts.
Time Complexity: O(log₃ n)
Rarely used in practice due to the added complexity and similar performance to binary search.
4. Jump Search
Jump Search works on sorted arrays and uses the idea of jumping ahead by a fixed number of steps and then performing linear search.
Optimal Jump Step: √n
Time Complexity: O(√n)
5. Exponential Search
This method is useful when the size of the array is unknown.
Steps:
- Start at index 1.
- Double the index until you find a value greater than the target or reach the end.
- Perform binary search in the found range.
Time Complexity: O(log i), where i is the position of the element
6. Fibonacci Search
A technique based on Fibonacci numbers. It divides the array into sections defined by Fibonacci series and compares accordingly.
Time Complexity: O(log n)
7. Hashing
Hashing is a technique to uniquely identify a specific object from a group of similar objects.
- Data is stored in a hash table.
- Uses a hash function to compute the index of the key.
Types of Hashing:
- Direct Addressing
- Mod Hashing
- Multiplicative Hashing
- Collision Resolution:
- Chaining
- Open Addressing (Linear/Quadratic/Double Hashing)
📌 Insert Diagram: Hash Table with Collision and Resolution Methods
8. Searching in Linked Lists
Unlike arrays, linked lists do not allow random access. Searching is done linearly.
Time Complexity: O(n)
9. Searching in Trees
Binary Search Tree (BST)
- Elements in the left subtree are smaller than the node.
- Elements in the right subtree are greater.
- Allows efficient search in O(log n) time for balanced BST.
📌 Insert Diagram: Binary Search Tree Showing Left and Right Subtrees
AVL Trees / Red-Black Trees
- Self-balancing BSTs
- Maintain O(log n) search time in all cases
10. Searching in Graphs
Two main approaches:
- Depth-First Search (DFS)
- Breadth-First Search (BFS)
Used in pathfinding, AI, network routing, etc.
📌 Insert Diagram: BFS and DFS Tree Traversal Graph
Comparison Table of Search Algorithms
| Search Method | Time Complexity (Avg) | Data Structure | Sorted Data Required | Space Complexity |
|---|---|---|---|---|
| Linear Search | O(n) | Array/List | No | O(1) |
| Binary Search | O(log n) | Array | Yes | O(1) |
| Jump Search | O(√n) | Array | Yes | O(1) |
| Exponential Search | O(log n) | Array | Yes | O(log n) |
| Fibonacci Search | O(log n) | Array | Yes | O(1) |
| Hashing | O(1) (Avg) | Hash Table | No | O(n) |
| DFS / BFS | O(V+E) | Graph | N/A | O(V) |
Important Definitions
- Search Key: The target element to be found.
- Hash Function: A function that maps data to a fixed-size index in a hash table.
- Collision: When two keys hash to the same index.
- Binary Search Tree: A tree structure where left < root < right.
- Traversal: Visiting all nodes systematically.
Short Answer Questions (2–3 mark)
Q1. What is the time complexity of binary search?
A: O(log n) in the best, average, and worst cases (only for sorted arrays).
Q2. Define hashing.
A: Hashing is a technique to map keys to indexes using a hash function for efficient searching.
Q3. What is the main disadvantage of linear search?
A: It has poor performance on large datasets with O(n) time complexity.
Long Answer Questions (5–10 mark)
Q1. Explain the working of binary search with an example.
A: Binary search works by repeatedly dividing a sorted array and checking the middle element.
Example: Searching 23 in [10, 20, 23, 40, 50]
- Step 1: mid = 2 (23), key found
- Only one comparison needed
Time Complexity: O(log n)
Q2. Compare hashing with binary search.
| Feature | Hashing | Binary Search |
|---|---|---|
| Data Requirement | No sorting | Requires sorting |
| Time Complexity | O(1) (avg) | O(log n) |
| Worst Case | O(n) (collisions) | O(log n) |
| Use Case | Large datasets | Moderate datasets |
| Storage | Needs extra space | In-place |
Q3. Describe depth-first and breadth-first search with applications.
- DFS uses a stack (recursion or explicit) and explores as far as possible.
- BFS uses a queue and explores all neighbors before going deeper. Applications:
- DFS: Solving puzzles, maze navigation
- BFS: Shortest path algorithms, AI, web crawling
Chapter Summary
•Searching means finding the position of a key in a data structure•Linear search is simple but inefficient•Binary search is fast but works only on sorted arrays•Jump, Exponential, and Fibonacci search improve over linear/binary•Hashing is ideal for constant time search with collision handling•Trees enable fast log n search in structured data•Graphs use DFS/BFS for traversal and search in networks•Choosing a search method depends on data type and size
Model Paper / Internal Questions
- Explain linear and binary search with code examples.
- Write an algorithm for jump search and analyze its complexity.
- Describe the working of hashing with suitable examples.
- What is collision in hashing? Explain different collision resolution techniques.
- Write a short note on DFS and BFS with applications.
- What are the advantages of binary search over linear search?
- Differentiate between hashing and binary search.
- Explain how search is performed in linked lists and trees.
- Discuss the need and application of exponential and ternary search.
- Define hash function and list its desirable properties.
Click below to download this chapter as PDF
Suggested file name: Search-Operation-Data-Structures-BTech-Notes-2025.pdf
