$ luctre

Recent Posts

See 10 more →

Learning Algorithms

3 min read

Motivation

Knowing how to implement certain algorithms will improve your problem-solving skills by expanding your toolkit. You will be able to recognize patterns when looking at a problem and identify which algorithm to apply in order to solve it.

Besides, there are many coding interviews that focus on algorithms and data structures, so knowing how to implement them will help you to perform better in these interviews, at least in the technical part.

Here I will cover the fundamental algorithms as I learn them myself, as well as some other ones that I find important.

Fundamental Algorithms

These are algorithms that are widely used as building blocks for solving more complex problems, and are also frequently asked in coding interviews.

This is the list I’m aiming for:

  1. BFS / DFS - Everything graph-related starts here
  2. Binary Search - Fundamentally different problem type
  3. Hash Tables - Essential for most optimization tricks
  4. Dynamic Programming - Core problem-solving approach
  5. Sorting - Just know one well (merge or quick)
  6. Stacks - Comes up surprisingly often

Binary search finds an element in a sorted array by repeatedly dividing the search area in half until the target is found.

WARNING

Binary search only works on sorted arrays.

The implementation consists on:

  1. Initializing two pointers, to mark the start and end of the search area
  2. Using these pointers to calculate the middle index of the current search area
  3. Comparing the element in the middle with the target element
  4. Tweak the pointers based on the comparison result:
  5. Repeat steps 2-4 until the target is found

How the comparison works:

  • If middle element is equal to the target, return the middle index
  • If the middle element is less than the target, move the start pointer to middle + 1
  • If the middle element is greater than the target, move the end pointer to middle - 1

This is called “binary” search because each comparison cuts the search area in half, making it highly efficient.

Here is a Python implementation of binary search:

def binary_search(arr: list[int], target: int) -> int:
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

The time complexity of binary search is O(log n).

NOTE

Binary Search works with any data type that supports comparison operations—not just integers—and it works on both odd and even length arrays.

Other Useful Algorithms

These are “nice to have but not critical”:

  • Two-pointer / Sliding window (really just array optimization tricks)
  • Heaps / Priority queues (useful but not foundational)
  • Recursion & Backtracking (flows from BFS/DFS and DP)

Maybe I will add more later, but for now is more than enough work to do.

Graph View