{"schemaVersion":"1.0","type":"TechArticle","types":["Article","TechArticle"],"slug":"algorithms-you-ll-actually-use-sorting-searching-recursion-and-beam-search-ji26o","url":"https://zyvop.com/algorithms-you-ll-actually-use-sorting-searching-recursion-and-beam-search-ji26o","title":"Algorithms You'll Actually Use: Sorting, Searching, Recursion, and Beam Search","subtitle":"Sorting, searching, recursion, dynamic programming, and beam search explained in plain language, with AI examples like chunking documents and fixing misspelled tool calls.","tldr":"You won’t invent new algorithms as an AI engineer, but you will use them every week. This post covers sorting, binary search, recursion, dynamic programming, sliding windows, and beam search, then builds a “did you mean?” helper for agent tool calls.","keywords":["Beam Search","Python","AI Engineer","Dynamic Programming","Algorithms","AI","Zero to Top AI Engineer (2026): Full Series Plan"],"entities":["Pradeep Kumar","Beam Search","Python","AI Engineer","Dynamic Programming","Algorithms","AI","Zero to Top AI Engineer (2026): Full Series Plan","ZyVOP"],"keyTakeaways":["An algorithm is just a step-by-step recipe for solving a problem.","\"To find a name in a phone book, open it in the middle, decide which half the name is in, and repeat\" is an algorithm.","You use them all the time without noticing."],"headings":["Sorting","How sorting works: divide and conquer","Searching","Binary search isn't just for lists","Recursion","Dynamic programming: don't solve the same problem twice","A real example: edit distance","Sliding windows: how text gets chunked","Top-k, again","Beam search: how models pick their words","Mini project: a \"did you mean?\" for tool calls","Make it yours","Practice","What to take away"],"outboundLinks":[],"contentText":"An algorithm is just a step-by-step recipe for solving a problem. \"To find a name in a phone book, open it in the middle, decide which half the name is in, and repeat\" is an algorithm. You use them all the time without noticing. You won't be inventing new sorting methods in an AI job. What you will do is choose between tools, spot a familiar pattern when you meet one, and read library documentation without being lost. This post covers the handful of ideas that come up again and again, with AI-flavored examples. It's skippable if you already know them. Here's a test. What does this print, and why would mystery(40) take very long to finish? What one-line change would fix that? def mystery(n): if n <= 1: return n return mystery(n - 1) + mystery(n - 2) print([mystery(i) for i in range(8)])If you said [0, 1, 1, 2, 3, 5, 8, 13] and could name the fix (hint: Post 8), skip to Post 18. Otherwise, read on. Sorting You'll almost never write a sort yourself. Python's sorted() and list.sort() use an algorithm called Timsort, which is fast, and stable, meaning items that compare as equal stay in their original order. Use key to say what to sort by (the function-as-argument idea from Post 6): docs = [ {\"title\": \"Beta\", \"score\": 0.8}, {\"title\": \"Alpha\", \"score\": 0.8}, {\"title\": \"Gamma\", \"score\": 0.9}, {\"title\": \"Delta\", \"score\": 0.5}, ] ranked = sorted(docs, key=lambda d: (-d[\"score\"], d[\"title\"])) print([d[\"title\"] for d in ranked]) # ['Gamma', 'Alpha', 'Beta', 'Delta']The key is a tuple. It sorts by score from highest to lowest (the minus sign flips the order), and breaks ties alphabetically by title. Putting a tuple in the key is the standard way to sort by several things at once. Stability shows up here: words = [\"pear\", \"fig\", \"apple\", \"kiwi\", \"plum\", \"date\"] print(sorted(words, key=len)) # ['fig', 'pear', 'kiwi', 'plum', 'date', 'apple']pear, kiwi, plum, and date all have four letters, and they stay in the order they started in. One gotcha trips up nearly everyone. sorted() returns a new list. .sort() changes the list in place and returns None: numbers = [3, 1, 2] result = numbers.sort() print(result) # None print(numbers) # [1, 2, 3]If you write numbers = numbers.sort(), you've just replaced your list with None. How sorting works: divide and conquer It's still worth seeing the idea once, because it appears all over computer science. Merge sort splits the list in half, sorts each half, and merges the two sorted halves: def merge_sort(items): if len(items) <= 1: return items middle = len(items) // 2 left = merge_sort(items[:middle]) right = merge_sort(items[middle:]) return merge(left, right) def merge(left, right): merged = [] i = j = 0 while i < len(left) and j < len(right): if left[i] <= right[j]: merged.append(left[i]) i += 1 else: merged.append(right[j]) j += 1 merged.extend(left[i:]) merged.extend(right[j:]) return mergedMerging two already-sorted lists is easy: keep comparing the front items and take the smaller. The function sorts by calling itself on smaller pieces, which is recursion (more on that below). Why is this fast? Halving a list of a million items takes about 20 splits to get down to single items, and each level of splitting does about a million units of merge work in total. So roughly (number of items) times (number of levels), which people write as n log n. A naive method that compares every item to every other grows as n times n, which gets painful quickly. Now the humbling part. On 100,000 random numbers, my merge sort took about 0.2 seconds, and the built-in sorted took about 0.02 seconds. The built-in is written in C and heavily tuned. Don't write your own sort in real code. Use it to understand the idea, then use sorted. One more point: don't sort when you don't need to. If you only want the top few items, a heap (Post 16) is cheaper. If you only want the biggest, use max. Searching Linear search checks items one at a time. It's what x in some_list does, and it's fine for short lists. For many lookups, build a set or dict first (Post 16), and every check becomes almost instant. When your data is already sorted, there's a smarter way, binary search. Look at the middle item. If it's too small, the target must be in the right half, so ignore the left half. If it's too big, ignore the right half. Repeat: def binary_search(items, target): low, high = 0, len(items) - 1 while low <= high: middle = (low + high) // 2 if items[middle] == target: return middle if items[middle] < target: low = middle + 1 else: high = middle - 1 return -1Each step throws away half of what's left. For a list of a million items, that means at most about 20 steps, instead of up to a million. In my test on a list of a million numbers, finding an item took 17 steps and confirming a missing one took 20. Binary search is famously easy to get slightly wrong (off-by-one errors in low, high, and middle). So in real code, use Python's built-in bisect module: import bisect scores = [10, 20, 30] print(bisect.bisect_left(scores, 25)) # 2 (where 25 would go) bisect.insort(scores, 25) print(scores) # [10, 20, 25, 30]bisect_left tells you the position where a value belongs in a sorted list, and insort inserts it there while keeping the list sorted. It's handy for things like finding which time range an event falls into. Binary search isn't just for lists Here's a trick that's useful in AI work. Suppose you want the largest batch size your GPU can handle without running out of memory. You can't look that up in a list, but you can test a size: it either works or it doesn't. And if size 40 works, so does everything below it. When a yes/no test flips only once like that, binary search finds the boundary in a handful of tries: LIMIT = 37 # pretend the real limit is 37 def fits(batch_size): return batch_size <= LIMIT def largest_batch_that_fits(max_size): low, high, best = 1, max_size, 0 while low <= high: middle = (low + high) // 2 if fits(middle): best = middle low = middle + 1 else: high = middle - 1 return best print(largest_batch_that_fits(512)) # 37It found the answer in 9 tries, testing 256, 128, 64, 32, 48, 40, 36, 38, and 37, instead of up to 512. When each test means loading a model and waiting a minute, that's a big difference. Searching comes up in AI in another way too. Vector search is the problem of finding the stored embeddings closest to a query. The brute-force method is a linear scan of every vector, which we sped up with NumPy in Post 15. When you have millions of vectors, systems use smarter indexes that skip most of the comparisons. We'll see how in Post 52. Recursion You met recursion in the last post. A recursive function solves a problem by calling itself on a smaller piece. It needs two things: a base case where it stops, and a step that moves toward that base case. A good example is flattening a list that contains lists inside lists, like the nested data a model might return: def flatten(items): flat = [] for item in items: if isinstance(item, list): flat.extend(flatten(item)) else: flat.append(item) return flat print(flatten([1, [2, [3, 4]], [[5]], 6])) # [1, 2, 3, 4, 5, 6]The base case is hiding in plain sight: an item that isn't a list gets appended directly, and the function stops going deeper. Recursion has limits. Every call adds to the call stack (Post 16), and Python caps how deep that can go: import sys print(sys.getrecursionlimit()) # 1000 def depth(n): return 0 if n == 0 else 1 + depth(n - 1) depth(5000) # RecursionError: maximum recursion depth exceededIf your data could be extremely deep, rewrite the function as a loop with an explicit stack, like the depth-first search from Post 16. Dynamic programming: don't solve the same problem twice Look back at the self-test. mystery(n) is the Fibonacci function, and it has a hidden problem. To compute mystery(5), it computes mystery(4) and mystery(3). But computing mystery(4) also computes mystery(3) again, and so on down the tree. The same small problems get solved over and over. Count the calls. Computing mystery(30) makes over 2.6 million calls, and every extra step multiplies the work by about 1.6. Adding 10 to n makes it roughly 100 times slower. Dynamic programming is the fix: remember each answer the first time you compute it. There are two styles. Top-down (memoization) is the easy one. You keep the recursive function and add a cache, which is the one-line fix from Post 8: from functools import cache @cache def fib(n): if n <= 1: return n return fib(n - 1) + fib(n - 2) print(fib(100)) # 354224848179261915075That answer arrives instantly, because each of the values from 0 to 100 is computed exactly once. Bottom-up (a table) fills in the small answers first and builds up, with no recursion at all: def fib_table(n): if n <= 1: return n a, b = 0, 1 for _ in range(n - 1): a, b = b, a + b return bHow do you spot a problem that suits this? Three signs: it splits into smaller versions of itself, those smaller versions repeat, and you're after a best, smallest, or count. A real example: edit distance Here's a dynamic programming problem you'll genuinely meet. How different are two strings? Edit distance counts the fewest single-character changes (insert, delete, or replace) needed to turn one into the other. Turning \"kitten\" into \"sitting\" takes 3. It powers spell checking, fuzzy matching, and de-duplication. And the word error rate that's used to score speech recognition systems is the same idea applied to words instead of letters. The smaller problems are \"the distance between the first few letters of each string.\" We fill in a table of those, and it turns out each cell only needs the cell above, the cell to the left, and the one diagonally up-left. That means we only need to remember the previous row: def edit_distance(a, b): previous = list(range(len(b) + 1)) for i, item_a in enumerate(a, start=1): current = [i] for j, item_b in enumerate(b, start=1): cost = 0 if item_a == item_b else 1 current.append( min( previous[j] + 1, # delete current[j - 1] + 1, # insert previous[j - 1] + cost, # replace (or keep) ) ) previous = current return previous[-1] print(edit_distance(\"kitten\", \"sitting\")) # 3The work is the length of a times the length of b, instead of exploding exponentially like the naive recursion. Sliding windows: how text gets chunked Here's a pattern you'll use soon. Language models and search systems can't take unlimited text, so long documents get cut into chunks. If you cut them cleanly with no overlap, a sentence that straddles the boundary gets split in half and loses its meaning. So chunks usually overlap a little. That's a sliding window: a window of fixed size that moves along the data, a few steps at a time. def chunk_words(words, size, overlap): if overlap >= size: raise ValueError(\"overlap must be smaller than size\") step = size - overlap chunks = [] for start in range(0, len(words), step): piece = words[start:start + size] if piece: chunks.append(piece) if start + size >= len(words): break return chunks numbers = list(range(1, 11)) print(chunk_words(numbers, 4, 1)) # [[1, 2, 3, 4], [4, 5, 6, 7], [7, 8, 9, 10]]Each chunk shares one item with the one before it. The window moves forward by size - overlap each time, and stops once it has reached the end. The check at the top matters: if the overlap were as big as the window, the step would be zero and the window would never move. We're chunking words here to keep things simple. Real systems usually count tokens, and try to split at sentence boundaries. We'll get into that in Post 54. Top-k, again You saw the idea in Post 16: to get the best k items from a big collection, don't sort everything. Keep a small heap, or use heapq.nlargest. It matters again in the next section. Beam search: how models pick their words Now an algorithm from the heart of AI. A language model writes text one token at a time. At each step it gives a probability to every possible next token. How do you turn that into a sentence? The simplest way is greedy: always take the most likely next token. It's fast, but short-sighted. A choice that looks best right now can lead somewhere worse overall. Beam search is less hasty. It keeps the best few partial sentences, called the beam, at every step. For each one it tries every possible next token, scores all those extended sentences by their total probability, and keeps only the top few. At the end, the best complete sentence wins. Here's a tiny pretend language model, a dictionary of \"given this word, here's how likely each next word is\": model = { \"<start>\": {\"the\": 0.55, \"a\": 0.45}, \"the\": {\"cat\": 0.34, \"dog\": 0.33, \"bird\": 0.33}, \"a\": {\"cat\": 0.9, \"dog\": 0.1}, \"cat\": {\"<end>\": 1.0}, \"dog\": {\"<end>\": 1.0}, \"bird\": {\"<end>\": 1.0}, }Greedy takes the first (0.55 beats 0.45). But after the, the probability is spread thin, with the best next word at only 0.34. So the cat has a total probability of 0.55 times 0.34, which is about 0.187. Whereas a cat is 0.45 times 0.9, which is 0.405. The sentence that started with the less likely first word is much more likely overall. Greedy can't see that, but beam search can. Here's both, in code. Notice that we add log probabilities instead of multiplying probabilities. Multiplying hundreds of small numbers produces a number so tiny the computer rounds it to zero (try 0.1 ** 400 and you'll get 0.0), while adding their logs stays perfectly stable: import heapq import math def greedy(model, max_len=5): words, log_prob = [\"<start>\"], 0.0 while words[-1] != \"<end>\" and len(words) < max_len: options = model[words[-1]] word = max(options, key=options.get) log_prob += math.log(options[word]) words.append(word) return words[1:], math.exp(log_prob) def beam_search(model, beam_width=2, max_len=5): beams = [(0.0, [\"<start>\"])] for _ in range(max_len): candidates = [] for log_prob, words in beams: if words[-1] == \"<end>\": candidates.append((log_prob, words)) continue for word, p in model[words[-1]].items(): candidates.append((log_prob + math.log(p), words + [word])) beams = heapq.nlargest(beam_width, candidates) if all(words[-1] == \"<end>\" for _, words in beams): break best_log_prob, best_words = beams[0] return best_words[1:], math.exp(best_log_prob) print(greedy(model)) # (['the', 'cat', '<end>'], 0.187) print(beam_search(model, beam_width=2)) # (['a', 'cat', '<end>'], 0.405)With a beam width of 1, beam search is the same as greedy. With a width of 2, it keeps both the and a alive after the first step, and the better ending wins. Look at what's inside: heapq.nlargest picking the top few candidates at every step. That's the top-k pattern from Post 16, doing real work. Two honest notes. A wider beam costs more, since you extend more candidates at every step, and it's not always better in practice. And chat models today often generate text by sampling instead, using settings like temperature, rather than beam search. Beam search has long been used for tasks like translation and speech recognition, where you want the single most likely output. Either way, understanding it shows you what's really happening when a model \"chooses\" its next word. Mini project: a \"did you mean?\" for tool calls Here's a real problem in agent apps. A model is asked to call a tool, and it spells the tool's name slightly wrong, such as get_wether instead of get_weather. Your code looks up the name, finds nothing, and crashes. A friendlier approach is to find the closest valid names and tell the model, so it can try again. That's edit distance, plus a heap, plus the error handling from Post 11. Create did_you_mean.py: import difflib import heapq def edit_distance(a, b): \"\"\"Fewest single-item edits (insert, delete, replace) to turn a into b.\"\"\" previous = list(range(len(b) + 1)) for i, item_a in enumerate(a, start=1): current = [i] for j, item_b in enumerate(b, start=1): cost = 0 if item_a == item_b else 1 current.append( min( previous[j] + 1, # delete current[j - 1] + 1, # insert previous[j - 1] + cost, # replace (or keep) ) ) previous = current return previous[-1] def did_you_mean(name, valid_names, max_distance=2, k=3): scored = [(edit_distance(name, valid), valid) for valid in valid_names] close = [pair for pair in scored if pair[0] <= max_distance] return [valid for distance, valid in heapq.nsmallest(k, close)] class ToolNotFoundError(Exception): pass def call_tool(name, tools): if name not in tools: suggestions = did_you_mean(name, list(tools)) hint = f\" Did you mean: {', '.join(suggestions)}?\" if suggestions else \"\" raise ToolNotFoundError(f\"Unknown tool {name!r}.{hint}\") return tools[name]() tools = { \"get_weather\": lambda: \"Sunny, 24 degrees\", \"get_time\": lambda: \"10:30\", \"search_web\": lambda: \"3 results\", \"send_email\": lambda: \"Sent\", \"set_timer\": lambda: \"Timer set\", } print(edit_distance(\"kitten\", \"sitting\")) print(did_you_mean(\"get_wether\", list(tools))) print(did_you_mean(\"set_time\", list(tools))) print(difflib.get_close_matches(\"get_wether\", list(tools), n=3, cutoff=0.6)) for name in [\"get_weather\", \"get_wether\", \"send_mail\", \"launch_rocket\"]: try: print(name, \"->\", call_tool(name, tools)) except ToolNotFoundError as error: print(name, \"-> error:\", error) reference = \"the cat sat on the mat\".split() heard = \"the cat sit on mat\".split() print(f\"word error rate: {edit_distance(reference, heard) / len(reference):.2f}\")You should see: 3 ['get_weather'] ['get_time', 'set_timer'] ['get_weather', 'get_time', 'set_timer'] get_weather -> Sunny, 24 degrees get_wether -> error: Unknown tool 'get_wether'. Did you mean: get_weather? send_mail -> error: Unknown tool 'send_mail'. Did you mean: send_email? launch_rocket -> error: Unknown tool 'launch_rocket'. word error rate: 0.33A few things to notice: The same edit_distance works on letters and on words. In the last lines we pass in lists of words and get a word error rate: 2 edits (one replaced word, one missing word) over 6 words, which is 0.33. The error message is written for the model. In a real agent loop, you'd feed that \"Did you mean...\" text back so the model can correct itself, the same trick as validating replies in Post 10. set_time returns two suggestions that are both one edit away, with ties broken alphabetically by the heap. difflib is the shortcut. Python's standard library has difflib.get_close_matches, which does a similar job. It uses a different similarity measure, so its results aren't identical: it returned get_time and set_timer as extra candidates for get_wether. Neither is \"right\". Pick the one that suits your data. Make it yours Add a test file using the techniques in Post 13. Include a property-based test that checks edit_distance(a, b) == edit_distance(b, a) and that edit_distance(a, a) == 0. Add @cache to a recursive version of edit distance and compare it with the table version. Make suggestions ignore case and underscores. Compute the word error rate between two real sentences of your own. Time did_you_mean against difflib with 10,000 valid names. Practice About 20 minutes of real effort on each before asking for help. Sort a list of dictionaries by two keys: one descending and one ascending. Write a binary search that returns where a value would be inserted, then compare it with bisect_left on lots of random lists. Write your own version of \"largest batch that fits\", using a fits function that you invent. Write a recursive function that returns how deeply a list is nested. Take a slow recursive function and speed it up with @cache. Time it before and after. Write a function that returns the word error rate between two sentences. Extend chunk_words so it chunks by sentences instead of words. Write a test that every word appears in at least one chunk. Change the toy model in the beam search example so that greedy and beam search agree, then so they disagree. Try beam widths of 1, 2, and 3. Then ask an AI tutor to review your answers, and don't let it rewrite them. What to take away Use sorted with a key. Sorting is stable, and a tuple key sorts by several things at once. Binary search needs sorted data and takes about 20 steps for a million items. It also works for any yes/no test that flips just once. Recursion needs a base case. For deep problems, switch to a loop with a stack. Dynamic programming means not solving the same problem twice. Add @cache, or fill in a table. Edit distance measures how different two strings are, and powers fuzzy matching. Sliding windows with overlap are how long text gets chunked. Beam search keeps the best few partial answers at every step, which beats greedy choices that look good now and turn out badly later. Previous: Post 16, Data Structures for AI Engineers Next in the series: Post 18, Big-O Without the Fear, where we put proper names on all this \"fast versus slow\" talk, and learn why complexity matters for vector search and batching.","contentHash":"sha256:77ac6d5ce0c71d9cae977109693854971aa3b19c9706ffb348bc4eec237386c7","authorName":"Pradeep Kumar","authorUrl":"https://zyvop.com/author/pradeep","authorSameAs":[],"category":"AI","tags":["Beam Search","Python","AI Engineer","Dynamic Programming","Algorithms"],"audience":"Software engineers and developers building applications with AI","tone":"Practical and evidence-based engineering guidance","readingTimeMinutes":14,"wordCount":3502,"faqs":null,"primaryTopic":"AI","publishedAt":"2026-10-27T07:35:32.825Z","updatedAt":"2026-10-27T07:35:32.825Z","canonicalUrl":"https://zyvop.com/algorithms-you-ll-actually-use-sorting-searching-recursion-and-beam-search-ji26o"}