Searching

Searching is the most common thing your code ever does — every \indexOf\, every database \WHERE\, every "does this user exist?" lookup is a search. The whole story is one trade-off: how much structure do you have in your data, and how much can you exploit? No structure → linear scan. Sorted → binary search. Sorted *and* uniformly distributed → interpolation search. Hash table → O(1). Pick the right one and a slow program becomes fast.

What "Searching" Actually Means

You have a collection and a *target*. You want one of:

• the index of the target (or −1 if absent),
• a boolean "is it here?",
• the closest element ≥ or ≤ the target,
• the best element satisfying some predicate.

Each variant has a slightly different algorithm shape. The first two are what people usually mean by "search"; the last two come up surprisingly often.

Linear Search (and Why It's Underrated)

Walk every element until you find it (or run out).

\\\`js function linear(arr, target) { for (let i = 0; i < arr.length; i++) { if (arr[i] === target) return i; } return -1; } \\\`

• Time: O(n) worst, O(1) best. Space: O(1).
• Needs nothing — works on any iterable, sorted or not, contiguous or not.

People treat linear search like a beginner mistake. It isn't. Use it when:

• The collection is small (n < ~30). The constant factor of binary search loses.
• The collection is unsorted and you'd only search once. Sorting costs O(n log n) — more than scanning.
• The data structure has no random access (linked list, stream).

Binary Search

The whole game is "the array is sorted, so I can throw away half each step".

\\\`js function binary(arr, target) { let lo = 0, hi = arr.length - 1; while (lo <= hi) { const mid = lo + ((hi - lo) >> 1); // overflow-safe midpoint if (arr[mid] === target) return mid; if (arr[mid] < target) lo = mid + 1; else hi = mid - 1; } return -1; } \\\`

O(log n). 30 steps for a billion-element sorted array. The whole algorithm fits on a napkin — and yet it's the algorithm that programmers most often get wrong.

Why \mid = lo + (hi - lo) / 2\ and not \(lo + hi) / 2\? In Java/C++/Go, \lo + hi\ can overflow a 32-bit int. The first form never does. JavaScript numbers are 64-bit floats so it's not strictly required, but the habit is cheap and right.

Beginner Mistakes to Skip

1. Off-by-one in bounds. \hi = arr.length\ (exclusive) and \hi = arr.length - 1\ (inclusive) need different loop conditions. Pick one convention and never mix. 2. Infinite loop. If you write \lo = mid\ (instead of \mid + 1\) when \lo == hi\, the search space stops shrinking. Always make sure one of the bounds strictly changes each iteration. 3. Searching unsorted data. Binary search silently returns wrong answers, not errors. Verify sorted-ness in tests. 4. \(lo + hi) / 2\ overflow in fixed-width languages. 5. Returning \mid\ on the first match when the problem asks for the *first* occurrence with duplicates. Different variant — see below. 6. Trusting \Array.prototype.includes\ / \indexOf\ to be O(log n) even on a sorted array. They're O(n) — they don't know it's sorted.

Intermediate: The Five Binary-Search Variants You'll Actually Use

Memorise the patterns, not the boundaries.

1. Exact match — the version above.

2. Lower bound (first index with \arr[i] >= target\):

\\\`js function lowerBound(arr, target) { let lo = 0, hi = arr.length; // hi exclusive while (lo < hi) { const mid = lo + ((hi - lo) >> 1); if (arr[mid] < target) lo = mid + 1; else hi = mid; } return lo; } \\\`

3. Upper bound (first index with \arr[i] > target\): same code, change \<\ to \<=\.

4. First occurrence of target: lower bound, then check \arr[lo] === target\. Last occurrence: upper bound minus one.

5. Search in rotated sorted array (\[4,5,6,7,0,1,2]\): each iteration, one half is still sorted. Detect which half, decide whether the target lies inside that half, recurse on the appropriate side. O(log n).

Intermediate: Binary Search on the Answer

The single most useful "trick" in competitive programming. If your problem has a monotonic feasibility predicate — "if x works, every value ≥ x also works" — you can binary-search the answer space without sorting anything.

\\\`js function smallestFeasible(lo, hi, isFeasible) { while (lo < hi) { const mid = lo + ((hi - lo) >> 1); if (isFeasible(mid)) hi = mid; else lo = mid + 1; } return lo; } \\\`

Plug in any \isFeasible\ and you've solved a whole class of problems:

• Koko Eating Bananas (LC 875) — smallest eating speed that finishes in time.
• Capacity to Ship Packages (LC 1011) — smallest ship capacity that meets the deadline.
• Split Array Largest Sum (LC 410) — smallest "max subarray sum" achievable.
• Aggressive Cows / Magnetic Force — largest minimum gap.
• Painter's Partition — smallest max workload.

When you see "minimise the maximum…" or "maximise the minimum…", reach instantly for binary search on the answer.

Intermediate: Hash Tables Beat Sorted Arrays for Membership

For "does this exist?", hash sets/maps are O(1) expected — strictly better than O(log n).

Need	Best structure
"is x here?"	hash set
"what's mapped to x?"	hash map
"smallest element ≥ x"	sorted array (binary search) or balanced BST
range queries	sorted array (lower_bound / upper_bound)
nearest neighbours	k-d tree, ball tree, BST

So binary search isn't always the answer; it's the answer when you also need *order*.

Advanced: Interpolation Search

Instead of always picking the middle, estimate where the target should be based on its value:

\\\` pos = lo + ((target - arr[lo]) * (hi - lo)) / (arr[hi] - arr[lo]) \\\`

For uniformly distributed sorted data (phone numbers, sequential IDs) this runs in O(log log n) on average — drastically faster than binary search at huge scale. Worst case (clustered or skewed data) degrades to O(n). Real systems rarely use it because hashed indexes already give O(1), but it's a beautiful idea.

Advanced: Exponential Search (Unbounded Arrays)

For sorted arrays where you don't know the size — say, an API that lets you query \arr[i]\ but won't tell you \length\:

1. Probe indices 1, 2, 4, 8, 16… (doubling) until \arr[i] >= target\ or \arr[i]\ is out of bounds. 2. Binary search inside \[i / 2, i]\.

Total: O(log n). Bonus: it's especially fast when the target is near the start of a huge array.

Advanced: Ternary Search

When the function you're searching isn't sorted but is unimodal (rises, then falls — or vice versa), divide the range into three parts using two midpoints \m1\, \m2\, and discard the third where the extremum can't lie. O(log n) to find the peak. This is what optimisation problems on a single variable use.

Don't use it for sorted-array search — binary is simpler and faster.

Advanced: Where Binary Search Quietly Lives

You meet binary search every day:

• STL / standard libraries: \std::lower_bound\, Python \bisect\, Java \Collections.binarySearch\, JS via libraries.
• Database B-tree indexes: every query against a sorted index does ~log(n) comparisons.
• Git bisect: binary search through commits to find a regression.
• Networking ACK windows: find the largest contiguous packet received.
• Floating-point square root in classic numerical libraries — binary search on the answer.

Advanced: Common Bugs and How to Avoid Them

Bug	Symptom	Fix
Infinite loop	hangs forever	ensure \lo\ or \hi\ strictly changes each step
Wrong half	finds wrong answer with duplicates	think carefully about \<\ vs \<=\
Off-by-one in result	always 1 short / over	match \hi = n\ exclusive vs \n - 1\ inclusive
Mid overflow	wrong index for huge arrays	\lo + (hi - lo) / 2\
Searching unsorted	returns wrong answer silently	sort first, or \assert\ sortedness
Comparing floats with \===\	misses targets	binary-search on a tolerance \hi - lo > eps\

Practice Path

1. Write \binary(arr, target)\ from scratch, then test on \[]\, \[5]\, \[1,3,5,7,9]\ (target 1, 5, 9, 4, 100). 2. Implement \lowerBound\ and \upperBound\. Use them to count how many times a value occurs in a sorted array in O(log n). 3. Solve Search in Rotated Sorted Array (LC 33). Trace it on \[4,5,6,7,0,1,2]\, target 0 and target 3. 4. Solve Koko Eating Bananas (LC 875) with binary search on the answer. Write the \canFinish(speed)\ predicate first, then plug it into the search.