Introduction #
If you’ve been coding for a while, you’ve probably noticed a pattern: no matter the programming language, framework, or shiny new library, the bedrock of software development is still algorithms. They are the silent workhorses that make our apps responsive, our data searchable, our recommendations accurate, and our systems scalable.
The good news? You don’t need to know every algorithm under the sun. But there’s a set of core, must-learn algorithms that show up again and again across domains—whether you’re building a web app, designing a database engine, training a machine learning model, or just trying to write efficient code for your next side project.
In this series, we’ll break down 14 of the most powerful algorithms every software developer should know. For each, we’ll dive into:
- Why the algorithm matters in practice.
- Its inner workings and step-by-step intuition.
- Time and space complexity (because Big-O isn’t just theory; it determines if your code melts in production).
- Real-world use cases where the algorithm shines.
- Implementation examples in Python and TypeScript (JavaScript).
Let’s start with a classic: Merge Sort.
Algorithm #1: Merge Sort #
Why Merge Sort Matters #
Imagine you’re building a backend for an e-commerce site. You’ve got thousands of products, and a user applies a “sort by price: low to high” filter. If your sorting is slow, the user is frustrated. If your sorting is fast and scalable, the experience feels seamless.
Sorting is a fundamental operation in computer science, and among the many sorting algorithms out there, Merge Sort stands out. It’s efficient, predictable, and forms the foundation for understanding the divide-and-conquer approach.
The Core Idea #
Merge Sort works by breaking down a big, messy problem (unsorted array) into smaller, manageable problems (tiny arrays), solving those, and then stitching the results back together in order. This “divide, conquer, combine” pattern is at the heart of many advanced algorithms.
Here’s how it works:
- Divide: Split the array into two halves.
- Conquer: Recursively sort each half.
- Combine: Merge the two sorted halves into a single sorted array.
This continues until you’re left with arrays of length 1 (which are trivially sorted).
A quick visual using Mermaid:
Complexity Analysis #
Time Complexity:
- Best case: O(n log n)
- Average case: O(n log n)
- Worst case: O(n log n)
Space Complexity: O(n) (needs extra space to store the merged results).
The predictability of O(n log n) is what makes Merge Sort popular in systems where worst-case performance matters (unlike Quick Sort, which can degrade to O(n²)).
Common Use Cases #
- Large datasets where stability matters: Merge Sort is stable, meaning equal elements keep their relative order—important for sorting by multiple keys (e.g., sort by department, then by salary).
- External sorting: When the dataset is too large to fit in memory (think log files or database records), merge sort can be adapted to work with chunks on disk.
- Functional programming: Because of its recursive nature, merge sort is elegant in functional languages where immutability is the norm.
Step-by-Step Example #
Let’s sort the array: [38, 27, 43, 3, 9, 82, 10].
Divide →
[38, 27, 43]and[3, 9, 82, 10].Recursively sort each:
[38, 27, 43]→[27, 38, 43].[3, 9, 82, 10]→[3, 9, 10, 82].
Merge results:
[27, 38, 43]+[3, 9, 10, 82]→[3, 9, 10, 27, 38, 43, 82].
Sorted!
Python Implementation #
def merge_sort(arr): if len(arr) <= 1: return arr mid = len(arr) // 2 left = merge_sort(arr[:mid]) right = merge_sort(arr[mid:]) return merge(left, right) def merge(left, right): result = [] i = j = 0 while i < len(left) and j < len(right): if left[i] <= right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 # Add remaining elements result.extend(left[i:]) result.extend(right[j:]) return result # Example usageprint(merge_sort([38, 27, 43, 3, 9, 82, 10]))
Output:
[3, 9, 10, 27, 38, 43, 82]
TypeScript Implementation #
function mergeSort(arr: number[]): number[] { if (arr.length <= 1) return arr; const mid = Math.floor(arr.length / 2); const left = mergeSort(arr.slice(0, mid)); const right = mergeSort(arr.slice(mid)); return merge(left, right);} function merge(left: number[], right: number[]): number[] { const result: number[] = []; let i = 0, j = 0; while (i < left.length && j < right.length) { if (left[i] <= right[j]) { result.push(left[i]); i++; } else { result.push(right[j]); j++; } } return result.concat(left.slice(i)).concat(right.slice(j));} // Example usageconsole.log(mergeSort([38, 27, 43, 3, 9, 82, 10]));
Output:
[3, 9, 10, 27, 38, 43, 82]
Key Insights #
- Merge Sort guarantees performance regardless of input order.
- It’s memory-heavy compared to in-place algorithms like Quick Sort.
- It’s a stepping stone to understanding recursive problem solving and divide-and-conquer strategies.
Up Next: Quick Sort — the fiery sibling of Merge Sort, faster in practice but riskier in the worst case.
Algorithm #2: Quick Sort #
Why Quick Sort Matters #
If Merge Sort is the reliable, predictable algorithm you call on when you can’t risk surprises, Quick Sort is the scrappy speed demon that gets things done in most real-world scenarios.
Quick Sort is one of the most widely used algorithms in practice. In fact, many programming languages’ built-in sort() functions (like in C, Python’s Timsort, or JavaScript’s V8 engine) are derived from Quick Sort or hybrids that include its logic. Why? Because when implemented well, it’s fast, in-place, and cache-friendly—qualities that matter a lot when you’re working with real applications, not just theory.
Imagine you’re building a recommendation engine where you need to sort results by relevance scores before serving them. If your sorting algorithm is inefficient, your users wait. Quick Sort is designed to minimize that wait.
The Core Idea #
Quick Sort is another divide-and-conquer algorithm, but instead of splitting arrays neatly in half like Merge Sort, it chooses a pivot element and then partitions the array around that pivot:
- Pick a pivot. This could be the first element, last element, middle element, or a random one.
- Partition the array. All elements smaller than the pivot go to the left; all greater go to the right.
- Recursively apply Quick Sort on the left and right subarrays.
When the recursion bottoms out (arrays of size 1), you’re left with a sorted array.
A simplified visual:
Complexity Analysis #
Time Complexity:
- Best case: O(n log n)
- Average case: O(n log n)
- Worst case: O(n²) (if pivots are poorly chosen, e.g., always smallest/largest element).
Space Complexity: O(log n) (for recursion stack, since it sorts in-place).
Despite the O(n²) worst case, Quick Sort tends to outperform Merge Sort in practice because it doesn’t need extra memory and works well with modern CPU caches.
Common Use Cases #
- Built-in sort implementations: Many libraries use Quick Sort or a variant.
- Database indexing: Sorting records quickly for efficient search.
- Competitive programming: It’s often the go-to algorithm due to its speed.
- Large datasets in memory: Because it’s in-place, Quick Sort is memory-efficient.
Step-by-Step Example #
Let’s sort [10, 7, 8, 9, 1, 5] with Quick Sort (pivot = last element):
- Pick pivot =
5. Partition:[1] [5] [10, 7, 8, 9]. - Quick Sort
[1]→ already sorted. - Quick Sort
[10, 7, 8, 9]: pivot =9. Partition:[7, 8] [9] [10]. - Quick Sort
[7, 8]: pivot =8. Partition:[7] [8]. - Combine:
[1, 5, 7, 8, 9, 10].
Sorted.
Python Implementation #
def quick_sort(arr): if len(arr) <= 1: return arr pivot = arr[-1] # last element as pivot left = [x for x in arr[:-1] if x <= pivot] right = [x for x in arr[:-1] if x > pivot] return quick_sort(left) + [pivot] + quick_sort(right) # Example usageprint(quick_sort([10, 7, 8, 9, 1, 5]))
Output:
[1, 5, 7, 8, 9, 10]
TypeScript Implementation #
function quickSort(arr: number[]): number[] { if (arr.length <= 1) return arr; const pivot = arr[arr.length - 1]; const left: number[] = []; const right: number[] = []; for (let i = 0; i < arr.length - 1; i++) { if (arr[i] <= pivot) { left.push(arr[i]); } else { right.push(arr[i]); } } return [...quickSort(left), pivot, ...quickSort(right)];} // Example usageconsole.log(quickSort([10, 7, 8, 9, 1, 5]));
Output:
[1, 5, 7, 8, 9, 10]
Key Insights #
- Quick Sort shines because of its average-case performance and low overhead.
- The choice of pivot matters. Randomized Quick Sort (choosing a random pivot) avoids the O(n²) pitfall in most cases.
- It’s an excellent way to learn about partitioning logic, which shows up again in algorithms like Quickselect (used to find the k-th smallest element).
- While Merge Sort is often preferred in distributed or disk-based systems, Quick Sort is usually the go-to when working in-memory.
Up Next: Heap Sort — less common in application code, but crucial to understanding priority queues, scheduling, and memory management.
Algorithm #3: Heap Sort #
Why Heap Sort Matters #
Heap Sort doesn’t always make the “fastest in practice” headlines (that honor usually goes to quicksort or Timsort), but it occupies a critical niche: deterministic O(n log n) performance with O(1) extra space. That combination is rare and valuable. When you need predictable performance, minimal memory overhead, and no recursion (or at least a bounded stack), Heap Sort is a strong choice.
Even more important: learning Heap Sort forces you to master the binary heap—a data structure that powers priority queues, job schedulers, event loops, graph algorithms (Dijkstra’s), top-K queries, streaming analytics, and more. In real-world systems, you’re far more likely to use a heap directly than to call heapsort itself. But knowing heapsort cements how heaps work, and gives you a mental model for why a priority queue delivers O(log n) inserts and deletes.
The Core Idea #
A binary heap is a complete binary tree where each node’s key is ≥ (max-heap) or ≤ (min-heap) the keys of its children. Heap Sort uses a max-heap to repeatedly extract the largest element and place it at the end of the array.
High-level steps (for ascending order):
Build a max-heap from the input array.
Repeat for
endfromn-1down to1:- Swap
arr[0](max element) witharr[end]. - Shrink the heap size by one (exclude the sorted tail).
- Heapify down from index
0to restore the heap.
- Swap
Because a binary heap is a complete tree, it maps cleanly into an array:
- Parent of
iis(i - 1) // 2 - Left child of
iis2*i + 1 - Right child of
iis2*i + 2
A tiny visual to anchor the idea:
In memory, this is just a flat array; the “tree” is conceptual.
Complexity and Characteristics #
Time Complexity:
- Building the heap: O(n) (bottom-up heapify).
- Each extract-max + heapify: O(log n).
- Performed
n-1times → total O(n log n).
Space Complexity: O(1) extra (in-place sort).
Stability: Not stable. Equal keys can reorder relative to each other.
Determinism: Worst case is still O(n log n) (unlike quicksort’s O(n²) worst case).
So why isn’t Heap Sort the default? Two reasons:
- Constant factors and cache behavior. Heaps jump around memory more than mergesort/quicksort, hurting cache locality.
- Stability. Many apps need stable sorting, where Timsort shines.
Where Heap Sort (and Heaps) Shine in Practice #
- Top-K problems: Find the largest K items from massive datasets (use a min-heap of size K).
- Streaming analytics: Maintain running percentiles/leaderboards.
- Schedulers and event loops: Always execute the next “most urgent” task via a priority queue.
- Graph algorithms: Dijkstra’s uses a min-priority queue to pick the next closest vertex.
- Memory-constrained environments: Need O(1) extra space and predictable performance.
- Partial sorting: Heaps are great when you don’t need a full sort—just the K best results.
Intuition: Bottom-Up Heap Build #
A common “aha” moment: building a heap is O(n), not O(n log n). We start heapifying from the last parent (n//2 - 1) down to 0. Most nodes are leaves or near leaves, so their heapify distances are short. Summed over all nodes, this yields linear time.
Step-by-Step Example #
Sort [4, 10, 3, 5, 1] ascending:
- Build max-heap → array might become
[10, 5, 3, 4, 1]. - Swap
arr[0]witharr[4]→[1, 5, 3, 4, 10]; heap size = 4. - Heapify down at
0→[5, 4, 3, 1, 10]. - Swap
arr[0]witharr[3]→[1, 4, 3, 5, 10]; heap size = 3. - Heapify →
[4, 1, 3, 5, 10]. - Swap
arr[0]witharr[2]→[3, 1, 4, 5, 10]; heap size = 2. - Heapify →
[3, 1, 4, 5, 10](at size 2, root becomes[1, 3]after next steps). - Eventually →
[1, 3, 4, 5, 10].
Pitfalls and Trade-offs #
- Not stable: If stability matters (e.g., multi-key sorts), choose mergesort or Timsort.
- Cache-unfriendly: Tree-like access patterns can be slower in practice.
- Don’t re-heapify top-to-bottom unnecessarily: Use the bottom-up build; it’s O(n).
- Prefer heaps for partial answers: If you only need top-K, use a heap of size K, not a full sort.
Python Implementation (In-Place Max-Heap, Ascending Sort) #
def heap_sort(arr): n = len(arr) def heapify_down(i, heap_size): while True: left = 2 * i + 1 right = 2 * i + 2 largest = i if left < heap_size and arr[left] > arr[largest]: largest = left if right < heap_size and arr[right] > arr[largest]: largest = right if largest == i: break arr[i], arr[largest] = arr[largest], arr[i] i = largest # Build max-heap (bottom-up) in O(n) for i in range(n // 2 - 1, -1, -1): heapify_down(i, n) # Repeatedly extract max to the end for end in range(n - 1, 0, -1): arr[0], arr[end] = arr[end], arr[0] heapify_down(0, end) return arr # Exampleif __name__ == "__main__": data = [4, 10, 3, 5, 1, 8, 2] print(heap_sort(data)) # [1, 2, 3, 4, 5, 8, 10]
Notes:
heapify_downrestores the heap invariant after pulling the max to the end.- The sort is in-place and uses O(1) extra memory.
- If you need descending order, build a min-heap (or reverse the result at the end).
TypeScript Implementation (In-Place Max-Heap, Ascending Sort) #
function heapSort(arr: number[]): number[] { const n = arr.length; function heapifyDown(i: number, heapSize: number): void { while (true) { const left = 2 * i + 1; const right = 2 * i + 2; let largest = i; if (left < heapSize && arr[left] > arr[largest]) largest = left; if (right < heapSize && arr[right] > arr[largest]) largest = right; if (largest === i) break; [arr[i], arr[largest]] = [arr[largest], arr[i]]; i = largest; } } // Build max-heap for (let i = Math.floor(n / 2) - 1; i >= 0; i--) { heapifyDown(i, n); } // Extract max to tail for (let end = n - 1; end > 0; end--) { [arr[0], arr[end]] = [arr[end], arr[0]]; heapifyDown(0, end); } return arr;} // Example usageconsole.log(heapSort([4, 10, 3, 5, 1, 8, 2])); // [1, 2, 3, 4, 5, 8, 10]
Practical Extensions and Variants #
- Min-heap vs. max-heap: For ascending sort with heapsort, we use a max-heap. If you switch to a min-heap, you would place the min at the beginning and grow from left to right, but that’s less convenient in-place.
- Partial sort / selection: For “largest K”, use a min-heap of size K—push items, and if size exceeds K, pop the smallest. Complexity: O(n log K), often far faster than sorting everything.
- Heaps in Dijkstra’s: Replace the “extract-min” step with a min-heap for O((V + E) log V) performance on sparse graphs.
- Median of a stream: Use two heaps (max-heap for lower half, min-heap for upper half) to maintain the median in O(log n) updates and O(1) queries.
When to Choose Heap Sort #
Pick Heap Sort when you need:
- O(1) extra space and deterministic O(n log n) performance.
- A non-recursive approach (you can write it iteratively).
- A teaching/demo tool to illuminate how priority queues work under the hood.
Prefer other sorts when you need:
- Stability (Timsort / mergesort).
- Best practical performance on real-world data (Timsort).
- Better cache locality (quicksort hybrids / Timsort).
Key Takeaways #
- Heap Sort is your space-efficient, worst-case safe sorting tool.
- Understanding heaps pays dividends across systems design, scheduling, and graph algorithms.
- In practice, you’ll use heaps constantly (priority queues), and heapsort occasionally—but learning it makes you a stronger engineer.
Up Next: Binary Search — the deceptively simple algorithm that silently powers databases, search boxes, and real-time systems by turning logarithms into speed.
Algorithm #4: Binary Search #
Why Binary Search Matters #
Few algorithms are as elegantly simple, yet as profoundly impactful, as Binary Search. At first glance, it looks like a toy example: find an item in a sorted list by repeatedly halving the search space. But under the hood, binary search is one of the most widely used building blocks in computer science.
Think of the last time you typed in a search bar, scrolled through an alphabetized contact list, or paginated through results in a database query. If the underlying dataset is sorted, binary search is quietly making things fast. Even beyond direct “search” problems, binary search serves as a general optimization technique—a way of homing in on solutions in logarithmic time.
The takeaway? If you master binary search deeply (including its tricky edge cases), you unlock not just the ability to search arrays, but also a framework for solving an entire family of problems.
The Core Idea #
At its heart, binary search follows a simple three-step loop:
- Start with a sorted array.
- Pick the middle element. Compare it with the target.
- If it matches, you’re done. If it’s smaller, eliminate the left half. If it’s larger, eliminate the right half.
- Repeat until the target is found or the search space is empty.
Each step halves the search space, making it logarithmically efficient.
A small visual with a target = 23:
Complexity and Characteristics #
Time Complexity:
- Best case: O(1) (if mid is the target immediately).
- Average/Worst case: O(log n).
Space Complexity:
- Iterative: O(1).
- Recursive: O(log n) (due to call stack).
Key requirement: the array must be sorted. If it isn’t, binary search results are meaningless.
Common Use Cases #
- Database indexes: B-trees and similar structures are optimized for binary search across disk pages.
- Search engines & autocomplete: Matching prefixes in sorted word dictionaries.
- Libraries & APIs: Functions like
bisectin Python orstd::lower_boundin C++ are binary search under the hood. - Optimization problems: Binary search on the answer (e.g., minimum feasible capacity, maximum valid value).
- Games and simulations: Adjusting difficulty levels, finding thresholds.
- Debugging performance: “Binary searching” through code commits or logs to find the source of a bug.
Step-by-Step Example #
Let’s search for 23 in [1, 4, 7, 15, 23, 42, 56, 70]:
- Start: low=0, high=7. Middle index = 3 → value = 15. 15 < 23 → search right half.
- Now low=4, high=7. Middle index = 5 → value = 42. 42 > 23 → search left half.
- Now low=4, high=4. Middle index = 4 → value = 23. Match found.
Pitfalls and Edge Cases #
Binary search is deceptively tricky to implement without off-by-one errors. Some common pitfalls:
- Midpoint calculation overflow: In languages with fixed integers,
(low + high) / 2can overflow. Safer:low + (high - low) // 2. - Infinite loops: If update rules don’t shrink the range, you’ll spin forever.
- Lower bound vs upper bound: Variants like “first element ≥ target” (lower bound) and “last element ≤ target” (upper bound) are incredibly useful, but require careful boundaries.
- Duplicates: Binary search finds an occurrence, but you may need the first/last.
Python Implementation #
def binary_search(arr, target): low, high = 0, len(arr) - 1 while low <= high: mid = low + (high - low) // 2 if arr[mid] == target: return mid elif arr[mid] < target: low = mid + 1 else: high = mid - 1 return -1 # Not found # Exampleprint(binary_search([1, 4, 7, 15, 23, 42, 56, 70], 23)) # 4print(binary_search([1, 4, 7, 15, 23, 42, 56, 70], 8)) # -1
TypeScript Implementation #
function binarySearch(arr: number[], target: number): number { let low = 0; let high = arr.length - 1; while (low <= high) { const mid = Math.floor(low + (high - low) / 2); if (arr[mid] === target) { return mid; } else if (arr[mid] < target) { low = mid + 1; } else { high = mid - 1; } } return -1; // Not found} // Example usageconsole.log(binarySearch([1, 4, 7, 15, 23, 42, 56, 70], 23)); // 4console.log(binarySearch([1, 4, 7, 15, 23, 42, 56, 70], 8)); // -1
Variants of Binary Search (Practical Gold) #
Binary search’s true power is in its variants:
- Lower Bound (First ≥ target): Find the first element not less than the target. Useful in range queries.
- Upper Bound (First > target): Find the last element less than or equal to the target.
- Binary Search on Answer: Common in competitive programming. Example: “What’s the minimum capacity of a ship to transport packages within D days?”
Python has this in bisect:
import bisectarr = [1, 4, 7, 15, 23, 42, 56, 70]print(bisect.bisect_left(arr, 23)) # 4print(bisect.bisect_right(arr, 23)) # 5
Real-World Example: Autocomplete #
Suppose you have a dictionary of words sorted alphabetically. A user types “car.” Binary search lets you quickly:
- Find the lower bound for “car” (first word ≥ “car”).
- Grab the next 10 entries.
- Return suggestions in O(log n + k) time (where k is number of suggestions).
Key Takeaways #
- Binary Search is more than “find an element”—it’s a general search framework.
- Its logarithmic performance makes it the default for searching sorted data.
- Variants like lower bound, upper bound, and binary search on the answer appear everywhere from databases to machine learning.
- Writing bug-free binary search is a rite of passage for every developer.
Up Next: Breadth-First Search (BFS) — the graph traversal that teaches you to think in waves, and underpins shortest-path algorithms, recommendation engines, and even solving puzzles like the Rubik’s Cube.
Algorithm #4: Binary Search #
Why Binary Search Matters #
Few algorithms are as elegantly simple, yet as profoundly impactful, as Binary Search. At first glance, it looks like a toy example: find an item in a sorted list by repeatedly halving the search space. But under the hood, binary search is one of the most widely used building blocks in computer science.
Think of the last time you typed in a search bar, scrolled through an alphabetized contact list, or paginated through results in a database query. If the underlying dataset is sorted, binary search is quietly making things fast. Even beyond direct “search” problems, binary search serves as a general optimization technique—a way of homing in on solutions in logarithmic time.
The takeaway? If you master binary search deeply (including its tricky edge cases), you unlock not just the ability to search arrays, but also a framework for solving an entire family of problems.
The Core Idea #
At its heart, binary search follows a simple three-step loop:
- Start with a sorted array.
- Pick the middle element. Compare it with the target.
- If it matches, you’re done. If it’s smaller, eliminate the left half. If it’s larger, eliminate the right half.
- Repeat until the target is found or the search space is empty.
Each step halves the search space, making it logarithmically efficient.
A small visual with a target = 23:
Complexity and Characteristics #
Time Complexity:
- Best case: O(1) (if mid is the target immediately).
- Average/Worst case: O(log n).
Space Complexity:
- Iterative: O(1).
- Recursive: O(log n) (due to call stack).
Key requirement: the array must be sorted. If it isn’t, binary search results are meaningless.
Common Use Cases #
- Database indexes: B-trees and similar structures are optimized for binary search across disk pages.
- Search engines & autocomplete: Matching prefixes in sorted word dictionaries.
- Libraries & APIs: Functions like
bisectin Python orstd::lower_boundin C++ are binary search under the hood. - Optimization problems: Binary search on the answer (e.g., minimum feasible capacity, maximum valid value).
- Games and simulations: Adjusting difficulty levels, finding thresholds.
- Debugging performance: “Binary searching” through code commits or logs to find the source of a bug.
Step-by-Step Example #
Let’s search for 23 in [1, 4, 7, 15, 23, 42, 56, 70]:
- Start: low=0, high=7. Middle index = 3 → value = 15. 15 < 23 → search right half.
- Now low=4, high=7. Middle index = 5 → value = 42. 42 > 23 → search left half.
- Now low=4, high=4. Middle index = 4 → value = 23. Match found.
Pitfalls and Edge Cases #
Binary search is deceptively tricky to implement without off-by-one errors. Some common pitfalls:
- Midpoint calculation overflow: In languages with fixed integers,
(low + high) / 2can overflow. Safer:low + (high - low) // 2. - Infinite loops: If update rules don’t shrink the range, you’ll spin forever.
- Lower bound vs upper bound: Variants like “first element ≥ target” (lower bound) and “last element ≤ target” (upper bound) are incredibly useful, but require careful boundaries.
- Duplicates: Binary search finds an occurrence, but you may need the first/last.
Python Implementation #
def binary_search(arr, target): low, high = 0, len(arr) - 1 while low <= high: mid = low + (high - low) // 2 if arr[mid] == target: return mid elif arr[mid] < target: low = mid + 1 else: high = mid - 1 return -1 # Not found # Exampleprint(binary_search([1, 4, 7, 15, 23, 42, 56, 70], 23)) # 4print(binary_search([1, 4, 7, 15, 23, 42, 56, 70], 8)) # -1
TypeScript Implementation #
function binarySearch(arr: number[], target: number): number { let low = 0; let high = arr.length - 1; while (low <= high) { const mid = Math.floor(low + (high - low) / 2); if (arr[mid] === target) { return mid; } else if (arr[mid] < target) { low = mid + 1; } else { high = mid - 1; } } return -1; // Not found} // Example usageconsole.log(binarySearch([1, 4, 7, 15, 23, 42, 56, 70], 23)); // 4console.log(binarySearch([1, 4, 7, 15, 23, 42, 56, 70], 8)); // -1
Variants of Binary Search (Practical Gold) #
Binary search’s true power is in its variants:
- Lower Bound (First ≥ target): Find the first element not less than the target. Useful in range queries.
- Upper Bound (First > target): Find the last element less than or equal to the target.
- Binary Search on Answer: Common in competitive programming. Example: “What’s the minimum capacity of a ship to transport packages within D days?”
Python has this in bisect:
import bisectarr = [1, 4, 7, 15, 23, 42, 56, 70]print(bisect.bisect_left(arr, 23)) # 4print(bisect.bisect_right(arr, 23)) # 5
Real-World Example: Autocomplete #
Suppose you have a dictionary of words sorted alphabetically. A user types “car.” Binary search lets you quickly:
- Find the lower bound for “car” (first word ≥ “car”).
- Grab the next 10 entries.
- Return suggestions in O(log n + k) time (where k is number of suggestions).
Key Takeaways #
- Binary Search is more than “find an element”—it’s a general search framework.
- Its logarithmic performance makes it the default for searching sorted data.
- Variants like lower bound, upper bound, and binary search on the answer appear everywhere from databases to machine learning.
- Writing bug-free binary search is a rite of passage for every developer.
Up Next: Breadth-First Search (BFS) — the graph traversal that teaches you to think in waves, and underpins shortest-path algorithms, recommendation engines, and even solving puzzles like the Rubik’s Cube.

Loading discussion...