DSA • Divide & Conquer

Binary Search, Quick Select & More

Break problems into subproblems, conquer recursively. Explore four essential divide & conquer algorithms with pseudocode, analysis, and practice.

Algorithms

📌 Divide & Conquer Paradigm: A problem is broken into smaller subproblems of the same type, solved recursively, and then their solutions are combined. This strategy yields efficient algorithms for searching, selection, matrix operations, and geometry.

🎯 In this module: Binary Search (logarithmic search), Quick Select (average linear selection), Strassen’s Matrix Multiplication (faster matrix product), and Closest Pair of Points (geometric divide & conquer).

Binary Search

O(log n) sorted iterative

Quick Select

O(n) avg k‑th partition

Strassen’s

O(n².⁸¹) matrix 7 mults

Closest Pair

O(n log n) geometry strip

1 Binary Search

How it works: Requires a sorted array. Repeatedly compares the target value with the middle element; if not equal, eliminates half of the remaining array from consideration. This halves the search space each step.

🔍 Binary Search — Pseudocode Infographic

function binarySearch(arr, target): low = 0 high = len(arr)-1 while low <= high: mid = (low+high) // 2 if arr[mid] == target: return mid elif arr[mid] < target: low = mid+1 else: high = mid-1 return -1

Recursive version follows same logic with base case low > high.

Complexity Analysis

Case	Time Complexity	Space Complexity
Best (target at mid)	O(1)	O(1)
Average / Worst	O(log n)	O(1) iterative, O(log n) recursive stack

Condition: The input array must be sorted. Binary search is the optimal comparison‑based search algorithm for random‑access data structures.

💡 Key Insight: Can be adapted to find first/last occurrence, floor/ceil, or in rotated sorted arrays. Many DSA problems rely on this template.

2 Quick Select

How it works: A selection algorithm to find the k‑th smallest (or largest) element in an unordered list. It uses the same partitioning logic as Quick Sort: after partitioning, the pivot is placed at its correct sorted position. If the pivot index equals k-1, we’ve found it; otherwise we recursively search the left or right partition.

🎯 Quick Select — Pseudocode Infographic

function quickSelect(arr, left, right, k): if left == right: return arr[left] pivotIndex = partition(arr, left, right) if k-1 == pivotIndex: return arr[pivotIndex] elif k-1 < pivotIndex: return quickSelect(arr, left, pivotIndex-1, k) else: return quickSelect(arr, pivotIndex+1, right, k) // partition() same as Quick Sort (Lomuto/Hoare)

Complexity Analysis

Case	Time Complexity	Space Complexity
Average	O(n)	O(log n) recursion stack
Worst (bad pivot choices)	O(n²)	O(n)

Stability: Not stable. In‑place: Yes (apart from recursion).

⚠️ Pivot Strategy: Random or median‑of‑three pivot selection reduces the chance of worst‑case to negligible in practice.

3 Strassen’s Matrix Multiplication

How it works: Standard matrix multiplication of two n×n matrices takes O(n³). Strassen’s algorithm reduces the number of multiplications for 2×2 block matrices from 8 to 7, recursively. It computes 7 intermediate products and then combines them with additions/subtractions. The asymptotic complexity becomes O(n^log₂7) ≈ O(n^2.81).

🔢 Strassen’s — Recursive Step Infographic

function strassen(A, B): if n <= threshold: return standardMultiplication(A, B) partition A, B into 4 submatrices (size n/2) compute 7 products: P1 = strassen(A11+A22, B11+B22) P2 = strassen(A21+A22, B11) P3 = strassen(A11, B12-B22) P4 = strassen(A22, B21-B11) P5 = strassen(A11+A12, B22) P6 = strassen(A21-A11, B11+B12) P7 = strassen(A12-A22, B21+B22) combine: C11 = P1+P4-P5+P7 C12 = P3+P5 C21 = P2+P4 C22 = P1-P2+P3+P6 return combined C

Complexity Analysis

Algorithm	Time Complexity	Space Complexity
Standard	O(n³)	O(1) (in‑place possible)
Strassen	O(n^2.81)	O(n²) extra for temp matrices

Practical note: Due to high constant factors and overhead, Strassen’s is often used only for very large matrices, sometimes in a hybrid approach with standard multiplication for small submatrices.

💡 Insight: Strassen’s algorithm shows that divide & conquer can break the O(n³) barrier for matrix multiplication. It’s a classic example of algorithm design reducing computational complexity.

4 Closest Pair of Points

How it works: Given n points in a 2D plane, find the pair with the smallest Euclidean distance. A naive O(n²) approach compares all pairs. The divide & conquer algorithm sorts points by x‑coordinate, recursively finds the closest distance in left and right halves, then checks a “strip” around the vertical dividing line. By only checking points within the strip that are close in y, it reduces the merging step to O(n) after sorting by y, yielding O(n log n) total time.

📍 Closest Pair — Pseudocode Outline Infographic

function closestPair(points sorted by x): if n <= 3: brute force mid = n/2 leftMin = closestPair(left half) rightMin = closestPair(right half) d = min(leftMin, rightMin) create strip of points within distance d of mid line sort strip by y for each point in strip: check next 7 points in y-order update d if closer pair found return d

Complexity Analysis

Step	Time Complexity	Space Complexity
Sorting by x	O(n log n)	O(n)
Divide & conquer recursion	O(n log n)	O(n) temporary arrays
Overall	O(n log n)	O(n)

Key detail: The strip checking step is O(n) because each point is compared with at most 7 others, making the merge linear.

💡 Application: Used in collision detection, clustering, and many geometric algorithms.

Comparative Summary

Algorithm	Use case	Time Complexity	Space Complexity	Key Requirement
Binary Search	Search in sorted array	O(log n)	O(1)	Sorted data
Quick Select	Find k‑th smallest/largest	O(n) avg, O(n²) worst	O(log n) stack	Random pivot for average case
Strassen’s	Multiply large matrices	O(n^2.81)	O(n²)	Square matrices, power of two size
Closest Pair	Computational geometry	O(n log n)	O(n)	Pre‑sort by x and y

Practice Problems

🔰 Beginner Level

1. Binary Search — First Occurrence

Problem: Modify binary search to return the index of the first occurrence of a target in a sorted array that may contain duplicates.

def first_occurrence(arr, target):
    low, high = 0, len(arr)-1
    result = -1
    while low <= high:
        mid = (low+high)//2
        if arr[mid] == target:
            result = mid
            high = mid-1      # keep searching left
        elif arr[mid] < target:
            low = mid+1
        else:
            high = mid-1
    return result

2. Quick Select — Find Median

Problem: Use quick select to find the median of an unsorted array. (If length even, return lower median.)

def find_median(arr):
    n = len(arr)
    k = (n+1)//2   # ceil(n/2)
    return quick_select(arr, 0, n-1, k)

⚡ Intermediate Level

3. Strassen’s for 2×2 Matrices

Problem: Implement Strassen’s multiplication for 2×2 matrices without recursion (just the 7 products and addition).

def strassen_2x2(A, B):
    a,b,c,d = A[0][0], A[0][1], A[1][0], A[1][1]
    e,f,g,h = B[0][0], B[0][1], B[1][0], B[1][1]
    p1 = (a+d)*(e+h)
    p2 = (c+d)*e
    p3 = a*(f-h)
    p4 = d*(g-e)
    p5 = (a+b)*h
    p6 = (c-a)*(e+f)
    p7 = (b-d)*(g+h)
    C11 = p1 + p4 - p5 + p7
    C12 = p3 + p5
    C21 = p2 + p4
    C22 = p1 - p2 + p3 + p6
    return [[C11,C12],[C21,C22]]

4. Closest Pair — Brute Force for Small n

Problem: Write the brute‑force O(n²) helper used when the number of points ≤ 3 in the recursive algorithm.

def brute_force_closest(points):
    min_dist = float('inf')
    n = len(points)
    for i in range(n):
        for j in range(i+1, n):
            dist = math.dist(points[i], points[j])
            if dist < min_dist:
                min_dist = dist
    return min_dist

Unsolved Practice

1. Binary Search in Rotated Sorted Array

Problem: Search for a target in a rotated sorted array (e.g., [4,5,6,7,0,1,2]). Return its index.

Write your solution here.

2. Quick Select to find Top K largest elements

Problem: Use partitioning to find the K largest elements of an array without fully sorting.

Write your solution here.

3. Implement full recursive Strassen’s for n×n matrices (n power of 2)

Problem: Write a recursive function that pads matrices to the next power of two and applies Strassen’s algorithm.

Write your solution here.

4. Closest Pair with Points Randomly Distributed

Problem: Implement the full O(n log n) closest pair algorithm including pre‑sorting and strip merging.

Write your solution here.