Explain the divide and conquer algorithm with an example in Java

By | March 23, 2023

Divide and conquer is a problem-solving algorithm that involves breaking down a problem into smaller sub-problems, solving them independently, and then combining their solutions to arrive at the solution for the original problem.

Here’s an example of how the divide and conquer algorithm can be implemented in Java:

Problem statement: Find the maximum number in an array of integers.

Solution using Divide and Conquer algorithm:

  1. Divide the array into two halves.
  2. Find the maximum number in the left half recursively by calling the same function on the left half.
  3. Find the maximum number in the right half recursively by calling the same function on the right half.
  4. Compare the maximum number from the left half with the maximum number from the right half and return the larger of the two.

Java code for implementing the above solution:

package Divide.And.Conquer;

public class DivideAndConquer {

public static int findMax(int[] arr, int left, int right) {

// Base case – If there is only one element in the array, return it
if (left == right) {
return arr[left];
}

// Divide the array into two halves
int mid = (left + right) / 2;

// Find the maximum number in the left half
int maxLeft = findMax(arr, left, mid);

// Find the maximum number in the right half
int maxRight = findMax(arr, mid + 1, right);

// Compare the maximum number from the left half with the maximum number from
// the right half and return the larger of the two
return Math.max(maxLeft, maxRight);
}

public static void main(String[] args) {

int[] arr = { 5, 10, 15, 20, 25, 30 };
int max = findMax(arr, 0, arr.length – 1);
System.out.println(“Maximum number in the array: ” + max);

}
}

Output:

Maximum number in the array: 30

In the above code, we have a function named findMax that takes an array, left index, and right index as parameters. The function recursively divides the array into two halves until there is only one element left in each sub-array. Then it compares the maximum number from the left half with the maximum number from the right half and returns the larger of the two. Finally, in the main function, we call the findMax function with the given array and its bounds to find the maximum number in the array.

Leave a Reply

Your email address will not be published. Required fields are marked *