optional · CSS study notes
Searching & Sorting (2017)
Overview — Two Distinct Problem Classes
- Searching: locating a target element within a data structure
- Sorting: arranging elements in a defined order (ascending/descending) — often a prerequisite for efficient searching (e.g., Binary Search needs sorted data)
Why They're Paired
- Sorting improves search efficiency: unsorted data → Linear Search O(n); sorted data → Binary Search O(log n)
- Trade-off: sorting has an upfront cost (O(n log n) typically) that only pays off if searches are repeated
Quick Reference Table
| Algorithm | Type | Best | Average | Worst | Space |
|---|---|---|---|---|---|
| Linear Search | Search | O(1) | O(n) | O(n) | O(1) |
| Binary Search | Search | O(1) | O(log n) | O(log n) | O(1) |
| Bubble Sort | Sort | O(n) | O(n²) | O(n²) | O(1) |
| Selection Sort | Sort | O(n²) | O(n²) | O(n²) | O(1) |
| Insertion Sort | Sort | O(n) | O(n²) | O(n²) | O(1) |
| Merge Sort | Sort | O(n log n) | O(n log n) | O(n log n) | O(n) |
| Quick Sort | Sort | O(n log n) | O(n log n) | O(n²) | O(log n) |
| Heap Sort | Sort | O(n log n) | O(n log n) | O(n log n) | O(1) |
Exam Angle
This overview table is your single most valuable memorization asset for the entire chapter — examiners frequently ask to "compare" 2-3 algorithms directly by time/space complexity. See dedicated pages for Binary Search, Merge Sort, Quick Sort, and Heap Sort for full mechanics.
📌 Sample & Repeated FPSC Questions (2016–2026)
2026, Paper I, Q5(a) (6 marks) — Why is Binary Search not suitable for an unsorted list?
Binary Search compares the target with the middle element and discards a half, relying on the guarantee that everything on one side is smaller (or larger) than the middle — a guarantee that only sortedness provides. On unsorted data, the target could be anywhere, so discarding a half based on one comparison can wrongly eliminate the half that actually contains it, producing an incorrect "not found" even when the value is present.
Key reasoning points:
- Precondition, not a performance issue: an unsorted list doesn't make Binary Search slower — it can make it wrong. On unsorted data you must use Linear Search O(n), or sort first (O(n log n)) if repeated searches are planned.
2024, Paper I, Q6(a) (8 marks) — For the following data sets, which sorting algorithms would work well, and which would not?
a. 10 floating-point values b. 1,000 integers c. 1,000 names d. 100,000 integers in [0,1000] e. 100,000 integers in [0, 1 billion] f. 100,000 names g. 1 million floating-point values h. 1 million names i. 1 million integers, uniform distribution j. 1 million integers, non-uniform distribution
| Dataset | Good choice | Why |
|---|---|---|
| a. 10 floats | Insertion Sort | tiny n — O(n log n) overhead not worth it |
| b. 1,000 ints | Quick/Merge Sort | O(n log n) comfortably beats O(n²) at this size |
| c. 1,000 names | Merge/Quick Sort | comparison-based, string cost per-compare but manageable |
| d. 100,000 ints, range [0,1000] | Counting Sort | O(n+k), k=1000 is small — beats any comparison sort |
| e. 100,000 ints, range [0,1B] | Quick/Merge/Radix Sort | Counting Sort impractical — k too large |
| f. 100,000 names | Merge/Quick Sort | good pivot/median strategy avoids Quick Sort's worst case |
| g. 1M floats | Merge Sort / Introsort | scales well at this size |
| h. 1M names | Merge Sort (stable) or MSD Radix | guaranteed O(n log n), stability often wanted for names |
| i. 1M ints, uniform | Bucket Sort | uniform distribution is Bucket Sort's ideal case — near O(n) |
| j. 1M ints, non-uniform | Quick/Merge/Heap/Radix Sort | Bucket Sort degrades badly — buckets fill unevenly |
Key reasoning points:
- This question tests whether you know sorting choice depends on data shape, not just size: small n → simple O(n²) sorts win on constants; known/limited value range → Counting Sort; uniform distribution → Bucket Sort; anything general-purpose/adversarial → comparison sorts with guaranteed O(n log n) (Merge/Heap) or good average case (Quick).
2017, Paper I, Q8(f) (5 marks) — Write short notes on: Searching Algorithms
Linear (Sequential) Search: examines each element in turn until found or the list ends. Works on sorted or unsorted data. Time: O(n) worst/average, O(1) best case. No pre-processing needed.
Binary Search: requires sorted data; compares target with the middle element and recurses into the half that can contain it. Time: O(log n) — far more efficient for large sorted datasets, at the cost of keeping the data sorted.
Other approaches worth naming: Hashing (average O(1) lookup via a hash function), Interpolation Search (improves on Binary Search for uniformly-distributed sorted data by estimating position rather than always halving), and tree/graph searches (BST search O(log n) average; BFS/DFS for graphs).
2026, Paper I, Q12 (MCQ, 1 mark) — In Hash Tables, what is a collision resolution technique?
- A. Linear Search
- B. Binary Search
- C. Chaining ✓
- D. None of these
MCQ Trap: Chaining stores every key that hashes to the same slot in a linked list at that slot — one of the two classic collision-resolution techniques (the other is open addressing). This is the searching-structure counterpart to Linear/Binary Search: hashing aims for average O(1) lookup, better than either.
📜 Past-Paper Questions & MCQs (CSS 2016–2026)
2024 · Paper-I · Q6(a) · 8 marks
Q. For the following data sets, which sorting algorithms would work well and which would not? (a) 10 floats (b) 1,000 integers (c) 1,000 names (d) 100,000 integers in 0–1,000 (e) 100,000 integers in 0–1 billion (f) 100,000 names (g) 1 million floats (h) 1 million names (i) 1 million integers, uniform (j) 1 million integers, non-uniform.
Ans.
| Data set | Works well | Works poorly |
|---|---|---|
| (a) 10 floats | Insertion sort (tiny input, simple) | None really; any sort is fine |
| (b) 1,000 integers | Quick, merge or insertion sort | None major |
| (c) 1,000 names | Merge sort (stable) or quick sort with string compare | Counting sort (not numeric) |
| (d) 100,000 integers, range 0–1,000 | Counting sort, O(n + k) with small k | Bubble or selection sort, O(n²) |
| (e) 100,000 integers, range 0–1 billion | Radix sort, quick, merge or heap sort | Counting sort (k is huge) and O(n²) sorts |
| (f) 100,000 names | Merge sort, quick sort, or MSD radix sort | O(n²) sorts |
| (g) 1 million floats | Quick, merge or heap sort, O(n log n) | Insertion, bubble sort |
| (h) 1 million names | Merge sort (stable, predictable) or multikey quick sort | O(n²) sorts |
| (i) 1 million integers, uniform | Bucket sort or radix sort, close to O(n) | O(n²) sorts |
| (j) 1 million integers, non-uniform | Quick, merge or heap sort | Bucket sort (buckets become unbalanced) |
- Rule: O(n²) sorts only suit very small inputs. For large inputs use O(n log n) comparison sorts, or non-comparison sorts when the key range is small or the data is uniform.
2017 · Paper-I · Q8(f) · 5 marks
Q. Write a short note on searching algorithms.
Ans.
- Searching means finding the position of a key in a collection of data. The main algorithms are:
| Algorithm | Idea | Needs sorted data? | Time |
|---|---|---|---|
| Linear (sequential) search | Check the elements one by one from the start | No | O(n) |
| Binary search | Compare with the middle element and discard half each time | Yes | O(log n) |
| Jump / interpolation search | Jump ahead in blocks, or estimate the position from the key value | Yes | O(√n) for jump search, O(log log n) average for interpolation on uniform data |
| Hashing | Compute the position of the key with a hash function | No | O(1) average |
| Tree search (BST, AVL) | Go left or right by comparing keys | Stored as a tree | O(log n) (O(n) for a skewed BST) |
- Worked example (binary search): array A = [3, 8, 15, 21, 34, 40], key = 21.
- Step 1: low = 0, high = 5, mid = (0 + 5) / 2 = 2, and A[2] = 15 < 21, so low = mid + 1 = 3.
- Step 2: low = 3, high = 5, mid = (3 + 5) / 2 = 4, and A[4] = 34 > 21, so high = mid − 1 = 3.
- Step 3: low = 3, high = 3, mid = (3 + 3) / 2 = 3, and A[3] = 21, so the key is found at index 3 after 3 comparisons.
- A linear search would need 4 comparisons for the same key.
- Choice: use linear search for small or unsorted data, binary search for sorted arrays, and hashing when the fastest lookup by key is needed.