Nitinn S Kulkarni

Posted on Apr 9

Part 7: Searching Algorithms in Python – Mastering Binary Search and Beyond

🚀 Introduction

Searching is one of the most common operations in programming, and binary search is the crown jewel — fast, efficient, and widely applicable.

In this post, we’ll explore:

✅ Linear Search vs Binary Search

✅ Binary search templates in Python

✅ Real-world problems using binary search

✅ Lower/Upper bound techniques

✅ Searching in rotated arrays and 2D matrices

🔎 1️⃣ Linear Search – Simple but Slow**


def linear_search(arr, target):
    for i, num in enumerate(arr):
        if num == target:
            return i
    return -1

📦 Time Complexity: O(n)

✅ Best for small or unsorted arrays

❌ Not efficient for large datasets

⚡ 2️⃣ Binary Search – Fast and Precise

Works on sorted arrays by dividing the search space in half at each step.


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

📦 Time Complexity: O(log n)

✅ Must be sorted

✅ Used in both 1D and 2D problems

🔁 3️⃣ Binary Search Template (Lower Bound Style)

This version is more flexible and forms the base of many variations.


def lower_bound(arr, target):
    left, right = 0, len(arr)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left

✅ Finds the first position where target can be inserted.

🧪 4️⃣ Real Problems Using Binary Search

🔹 Search Insert Position


def search_insert(nums, target):
    left, right = 0, len(nums)
    while left < right:
        mid = (left + right) // 2
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left

🔹 Find First and Last Position of an Element


def find_first_last(nums, target):
    def find_bound(is_left):
        left, right = 0, len(nums)
        while left < right:
            mid = (left + right) // 2
            if nums[mid] > target or (is_left and nums[mid] == target):
                right = mid
            else:
                left = mid + 1
        return left

    left = find_bound(True)
    right = find_bound(False) - 1
    if left <= right and right < len(nums) and nums[left] == target and nums[right] == target:
        return [left, right]
    return [-1, -1]

🔹 Search in Rotated Sorted Array


def search_rotated(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1

🔹 Binary Search in 2D Matrix


def search_matrix(matrix, target):
    if not matrix or not matrix[0]:
        return False

    m, n = len(matrix), len(matrix[0])
    left, right = 0, m * n - 1

    while left <= right:
        mid = (left + right) // 2
        val = matrix[mid // n][mid % n]
        if val == target:
            return True
        elif val < target:
            left = mid + 1
        else:
            right = mid - 1

    return False

🎯 5️⃣ Advanced Use Cases

🔸 Minimize the Maximum (Binary Search on Answer)

Use binary search on the value space, not index. Example:

- Minimum capacity to ship packages in D days


Min max distance to place routers
Minimize largest subarray sum

📊 6️⃣ Comparison Summary

Method	Time	Use Case
Linear Search	O(n)	Unsorted or small datasets
Binary Search	O(log n)	Sorted 1D arrays
2D Binary Search	O(log m*n)	Sorted matrices
Binary on Answer	Varies	Optimization problems

✅ Best Practices

✔️ Always check if the array is sorted before applying binary search
✔️ Use while left < right or while left <= right as per problem
✔️ Avoid infinite loops: always update left/right
✔️ Try implementing both upper and lower bound logic
✔️ For rotated arrays – think in terms of sorted halves

🧠 Summary

✔️ Binary search is the go-to method for efficient searching in sorted data
✔️ Understand different templates for flexible use
✔️ Learn to use it in 1D, 2D, and even on value space
✔️ A must-have technique for interviews and system optimization

🔜 Coming Up Next:

👉 Part 8: Trees and Binary Trees – Traversals, Depth, and Recursive Patterns

We’ll cover:

1. DFS & BFS


Inorder, Preorder, Postorder
Balanced trees, height, diameter
Binary Search Tree (BST) basics

DEV Community