Skip to content

Divide and Conquer

2.2.2 Computational methods · Paper 2 · 1 flashcard

Questions
Definition
Divide and conquer is a strategy that breaks a problem into smaller parts, solves each part, then merges solutions. The three steps are: divide, conquer, and merge.
Worked Example
Divide and Conquer: Binary Search
pseudocode 
function binarySearch(array, target, low, high):
    // Base case: element not found
    if low > high then
        return -1
    end if
    
    // DIVIDE: Find middle
    mid = (low + high) DIV 2
    
    // CONQUER: Check middle element
    if array[mid] == target then
        return mid
    elseif array[mid] > target then
        // Search left half
        return binarySearch(array, target, low, mid - 1)
    else
        // Search right half
        return binarySearch(array, target, mid + 1, high)
    end if
end function
Efficiency: Binary search halves the search space each time - O(log n) complexity.

Other examples: Quicksort, Mergesort