Searching Algorithms: Linear Search vs Binary Search
Unit 5: Searching, Sorting, Dynamic Memory & File Handling • Problem Solving Using C
👨🏫 Professor's Mental Model: Flipping Every Page in a Novel vs Opening an Oxford Dictionary
Linear Search ek aisi novel padhne jaisa hai jisme aap pehle page se aakhri page tak ek-ek word check karte ho—agar word aakhri page par hai toh bohot time lagega O(N)! Binary Search ek Oxford Dictionary dekhne jaisa hai: aap dictionary ko beech se kholte ho (Mid), agar word aage hai toh pichla aadha hissa fek dete ho! Har step me search area aadhi (N/2) ho jati hai, isliye 10 lakh items me se bhi sirf 20 steps me answer mil jata hai O(log N)! Lekin shart yeh hai ki dictionary SORTED honi chahiye!
Academic Lecture Notes & Solved Study Pages
Unit 5 • Core Concepts, Step-by-Step Proofs & Notebook Solutions
1. Linear Search (Sequential Search): Algorithm & Analysis
2. Binary Search (Divide and Conquer): Algorithm & Precondition
1. Maintain pointers: `low = 0`, `high = N - 1`.
2. Compute midpoint safely: `mid = low + (high - low) / 2` (Prevents integer overflow bugs caused by `(low + high) / 2` when values exceed 2 billion!).
3. If `arr[mid] == key`: Search is successful, return `mid`.
4. If `key < arr[mid]`: Search the left sub-array (`high = mid - 1`).
5. If `key > arr[mid]`: Search the right sub-array (`low = mid + 1`).
6. Repeat while `low <= high`. If `low > high`, element does not exist.
3. Computational Complexity Comparison
Consider searching in an array of $N = 1,000,000$ (One Million) items:
Binary search transforms an otherwise intractable problem into sub-microsecond retrieval.
| Parameter | Linear Search | Binary Search |
|---|---|---|
| Algorithm Paradigm | Sequential Iterative Scan | Divide and Conquer |
| Array Ordering Precondition | None: Works on unsorted and sorted arrays | Mandatory: Array MUST be strictly sorted |
| Best-Case Time Complexity | O(1) (Found at index 0) | O(1) (Found at middle index) |
| Worst-Case Time Complexity | O(N) (Linear time) | O(log2 N) (Logarithmic time) |
| Space Complexity | O(1) Auxiliary Space | O(1) for iterative; O(log N) for recursive |
| Suitable Data Structures | Arrays, Singly/Doubly Linked Lists | Arrays with random access (inefficient for lists) |
Interactive Tested Code Example
#include <stdio.h>
// Iterative Binary Search with Integer Overflow Safeguard
int binary_search(const int arr[], int size, int target) {
int low = 0;
int high = size - 1;
while (low <= high) {
// Safe midpoint calculation preventing integer overflow
int mid = low + (high - low) / 2;
if (arr[mid] == target)
return mid; // Target found at index 'mid'
else if (arr[mid] < target)
low = mid + 1; // Discard left half
else
high = mid - 1; // Discard right half
}
return -1; // Target not found
}
int main(void) {
int sorted_data[] = {11, 24, 35, 47, 59, 68, 73, 88, 92};
int size = sizeof(sorted_data) / sizeof(sorted_data[0]);
int search_key = 59;
int index = binary_search(sorted_data, size, search_key);
printf("=== BINARY SEARCH ENGINE ===\n");
if (index != -1)
printf("Success: Key %d located at array index [%d].\n", search_key, index);
else
printf("Failure: Key %d is not present in the array.\n", search_key);
return 0;
}🎯 University Exam Scoring Blueprint
- In university exams, always state the precondition for Binary Search: the array MUST be sorted.
- Explain why mid = low + (high - low) / 2 is used instead of (low + high) / 2 to avoid 32-bit integer overflow.
- Derive the recurrence relation for Binary Search: T(N) = T(N/2) + O(1) -> O(log N).