/ #Algorithms 

Algorithms Techniques - Part 4: Divide and Conquer

An overview of Divide and Conquer algorithms.

Divide and Conquer is a paradigm that solves a problem by breaking it down into two or more subproblems of the same - or related - type as the main problem. Each subproblem is then solved individually and their results are merged to form the final answer to the original problem. Some well known algorithms that use this method are Merge Sort and Quicksort.

Finding the max and min values in an array

Another problem that can be solved using Divide and Conquer is to find the maximum and minimum numbers in an array. The problem is really simple: given an array of n elements, find the maximum and the minimum number.

Let’s start with the straightforward approach:

  1. Initialize min and max variables with the first element in the array.
  2. Iterate the array and, for each element, get the min and max between min, max and the current element.
package main

import (
    "fmt"
)

// Helper function to find the minimum between two integers.
func minOf(a, b int) int {
    if a < b {
        return a
    }

    return b
}

// Helper function to find the maximum between two integers.
func maxOf(a, b int) int {
    if a > b {
        return a
    }

    return b
}

func MinMax(nums []int) (int, int) {
    min := nums[0]
    max := nums[0]

    var i int
    for i = 0; i < len(nums); i++ {
        min = minOf(min, nums[i])
        max = maxOf(max, nums[i])
    }

    return min, max
}

func main() {
    nums := []int{9, 5, 6, 8, 9, 6, 7, 10, 1, 2, 4, 3, 5}

    min, max = MinMax(nums)
    fmt.Printf("Min=%d, Max=%d\n", min, max)
}

This is a simple but quite efficient algorithm that will solve the problem in O(n). Not bad, but it can be improved.

Finding the min and max, Divide and Conquer version

Before we continue, let me tell you that the DaC version of this algorithm still runs in O(n). But, the number of comparisons can be greatly reduced, which can improve performance when the input array is big enough. If you are curious, the actual complexities for an array of size n are:

  • 2n - 2 for the no DaC version
  • 3(n/2) - 2 for the DaC version

Or something like that. :)

Now, let’s get to the algorithm. Following the idea behind DaC, we should divide the array in smaller chunks until they are small enough and then we solve the actual problem, finding min and max, and merge the results:

  1. Divide the array in smaller subarrays.
  2. Find the min and max of each subarray.
  3. The min and max of the original array should be the min and max of the subarrays.

For example:

  1. Given the array A = [1, 2, 5, 3, 8, 10], divide it in two subarrays A1 = [1, 2, 5] and A2 = [3, 8, 10].
  2. The min and max of each subarray will be
    • A1: min = 1, max = 5
    • A2: min = 3, max = 10
  3. The min of A will be min of [1, 3] (the min of A1 and A2)
  4. The max of A will be max of [5, 10] (the max of A1 and A2)

With that in mind, let’s get to the actual code:

package main

import (
    "fmt"
)

// Helper function to find the minimum between two integers.
func minOf(a, b int) int {
    if a < b {
        return a
    }

    return b
}

// Helper function to find the maximum between two integers.
func maxOf(a, b int) int {
    if a > b {
        return a
    }

    return b
}

func MinMax(nums []int) (int, int) {
    min := nums[0]
    max := nums[0]

    return min, max
}

// MinMax finds the minimum and maximum using Divide and Conquer.
// The first parameter is the array to find the min and max. The second and
// third parameters, left and right, are used as boundaries of the subarray
// we will find the min and max.
func MinMax(nums []int, left int, right int) (int, int) {
    // Calculate the length based on the left and right indexes.
    len := right - left + 1

    // Base cases
    if len == 1 {
        // Left and Right are the same
        return nums[left], nums[right]
    }

    if len == 2 {
        min := minOf(nums[left], nums[right])
        max := maxOf(nums[left], nums[right])

        return min, max
    }

    // Divide and Conquer
    mid := left + (right - left) / 2
    rightMin, rightMax := MinMax(nums, left, mid)
    leftMin, leftMax := MinMax(nums, mid+1, right)

    // Merge results
    return minOf(rightMin, leftMin), maxOf(rightMax, leftMax)
}

func main() {
    nums := []int{9, 5, 6, 8, 9, 6, 7, 10, 1, 2, 4, 3, 5}

    min, max = MinMax(nums, 0, len(nums) - 1)
    fmt.Printf("Min=%d, Max=%d\n", min, max)
}

Cover picture by Mildly Useful via Unsplash