Learning Algorithms

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.

In this post, I will be adding algorithms as I learn how to implement them, so I can refer back to them later and hopefully help you to learn them too.

This is a curated list of algorithms that I find important to know, and that I have used in the past to solve problems.

Divide and Conquer

Is a family of algorithms that are useful for problems that can be broken down into smaller, similar subproblems, such as sorting and searching algorithms.

Binary Search

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.