Chapter 13 — Searching Patterns

Chapter 13 — Searching Patterns

Hey everyone! Welcome back to Namaste DSA!

We've learned several ways to find things: scan linearly, binary search, or hash. This short chapter ties Season 3 together by answering the real interview skill: which searching tool should I reach for? Picking the right one is often the difference between O(n²) and O(n).

What we will cover:

• Linear search — and when it's actually fine
• Sorting first to unlock binary search
• Hashing vs sorting vs searching — the decision
• Two-pointer search on sorted data
• Interview Questions

---

1. Linear Search — And When It's Fine

Walking through every element is O(n). It feels "slow," but it's the right choice when:

✔ The data is UNSORTED and you'll search only once
✔ The array is tiny
✔ You need every match, not just one
✔ Sorting first would cost more than the single search

Don't sort a 10-element array just to binary search it once — the sort costs more than the scan.

---

2. Sorting First to Unlock Binary Search

If you'll search the same data many times, paying O(n log n) once to sort, then O(log n) per query, beats O(n) per query.

┌─────────────────────────────────────────────────────────────┐
│   ONE search:    linear O(n)  beats  sort O(n log n)        │
│   MANY searches: sort once O(n log n) + O(log n) each WINS  │
│                                                             │
│   Break-even: roughly when #queries > log n                 │
└─────────────────────────────────────────────────────────────┘

---

3. Hashing vs Sorting vs Searching — The Decision

You need...	Best tool	Cost
Fast "is x present?" lookups	Hash Set	O(1) avg per lookup
Range queries / k-th smallest / ordered data	Sort + binary search	O(n log n) + O(log n)
One-time search, unsorted	Linear search	O(n)
Find a pair/triplet with a sum	Sort + two pointers, or hashing	O(n log n) / O(n)

DECISION HINTS:
  "exists?" / "duplicate?" / "seen before?"   → Hash Set/Map  O(1)
  "k-th / smallest / range / closest"          → Sort then binary search
  "pair/triplet sums to X" on sortable data    → Sort + two pointers
  data already sorted                          → binary search directly

---

4. Two-Pointer Search on Sorted Data

A reminder from Chapter 06: once data is sorted, two pointers can search for pairs in O(n) without the log factor of binary search — and with O(1) space.

// 3-Sum sketch: sort, then for each i, two-pointer the rest
function threeSum(nums) {
    nums.sort((a, b) => a - b);          // O(n log n)
    const res = [];
    for (let i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) continue;  // skip dups
        let l = i + 1, r = nums.length - 1;
        while (l < r) {
            const sum = nums[i] + nums[l] + nums[r];
            if (sum === 0) { res.push([nums[i], nums[l], nums[r]]); l++; r--; }
            else if (sum < 0) l++;
            else r--;
        }
    }
    return res;
}
// Overall O(n²) — far better than the brute-force O(n³).

---

Interview Questions — Quick Fire!

Q: When is linear search the right choice over binary search?

"When the data is unsorted and you'll search it only once, or the array is small. Sorting to enable binary search costs O(n log n), which isn't worth it for a single lookup — the linear O(n) scan is cheaper overall."

Q: How do you decide between hashing and sorting?

"If you only need membership or counting — 'does x exist', 'how many times' — use a hash structure for O(1) average operations. If you need order-based queries like ranges, k-th smallest, or closest values, sort and binary search since hashing doesn't preserve order."

Q: For finding a pair with a given sum, what are your options?

"If the array is unsorted, a hash map gives O(n) using the 'seen before' trick. If it's sorted or you can sort it, two pointers from both ends give O(n) with O(1) space — total O(n log n) including the sort."

Q: Why sort before applying two pointers in 3-Sum?

"Sorting lets you move the two inner pointers based on whether the sum is too big or too small, and makes it easy to skip duplicates. It turns the brute-force O(n³) into O(n²)."

---

Quick Recap

Concept	Key Takeaway
Linear search	Fine for unsorted, one-time, small.
Sort first	Worth it for many queries (> log n).
Hash	"exists/seen/count" → O(1) avg.
Sort + binary/2-ptr	Order-based & pair-sum queries.

What's Next?

That completes Season 3! Next is Season 4 — Non-Linear Data Structures, starting with Chapter 14: Trees & Binary Trees — and all the traversals you'll be asked about in interviews.

Keep coding, keep grinding! See you in the next one!