Binary Search based problems

What is Divide and Conquer Algorithm?

Divide and Conquer is a problem-solving technique that involves breaking a larger problem into subproblems, solving the subproblems independently and combining the solutions of those subproblems to get the solution of the larger problem....

Stages of Divide and Conquer Algorithm:

Divide and Conquer Algorithm can be divided into three stages: Divide, Conquer and Merge....

Applications of Divide and Conquer Algorithm:

Merge Sort: Merge sort is a classic example of a divide and conquer sorting algorithm. It breaks down the array into smaller subarrays, sorts them individually, and then merges them to obtain the sorted array. Median Finding: The median of a set of numbers can be found using a divide and conquer approach. By recursively dividing the set into smaller subsets, the median can be determined efficiently. Min and Max finding: Divide and Conquer algorithm can be used to find both the minimum and maximum elements in an array simultaneously. By splitting the array into halves and comparing the min-max pairs from each half, the overall min and max can be identified in logarithmic time complexity. Matrix Multiplication: Strassen’s algorithm for matrix multiplication is a divide and conquer technique that reduces the number of multiplications required for large matrices by breaking down the matrices into smaller submatrices and combining their products. Closest Pair problem: The closest pair problem involves finding the two closest points in a set of points in a multidimensional space. A divide and conquer algorithm, such as the “divide and conquer closest pair” algorithm, can efficiently solve this problem by recursively dividing the points and merging the solutions from the subproblems....

Basics of Divide and Conquer Algorithm:

Introduction to Divide and Conquer Dynamic Programming vs Divide-and-Conquer Decrease and Conquer Advanced master theorem for divide and conquer recurrences...

Standard Algorithms on Divide and Conquer Algorithm:

Binary Search Merge Sort Quick Sort Calculate pow(x, n) Karatsuba algorithm for fast multiplication Strassen’s Matrix Multiplication Convex Hull (Simple Divide and Conquer Algorithm) Quickhull Algorithm for Convex Hull...

Binary Search based problems:

Find a peak element in a given array Check for Majority Element in a sorted array K-th Element of Two Sorted Arrays Find the number of zeroes Find the Rotation Count in Rotated Sorted array Find the point where a monotonically increasing function becomes positive first time Median of two sorted arrays Median of two sorted arrays of different sizes The painter’s partition problem using Binary Search...

Practice problems on Divide and Conquer Algorithm:

Square root of an integer Maximum and minimum of an array using minimum number of comparisons Find frequency of each element in a limited range array in less than O(n) time Tiling Problem Count Inversions The Skyline Problem Search in a Row-wise and Column-wise Sorted 2D Array Allocate minimum number of pages Modular Exponentiation (Power in Modular Arithmetic)...