BSCS | DSA Notes Algorithms – Divide and Conquer
DIVIDE AND CONQUER ALGORITHMS
Comprehensive Notes & Implementation Guide
Topic Algorithms Paradigm Divide & Conquer Focus C++ Implementation
1. Introduction to Divide and Conquer Algorithms
1.1 Definition
Divide and Conquer is a fundamental algorithm design paradigm in which a problem is:
1. Divided into smaller subproblems
2. Conquered by solving each subproblem recursively
3. Combined to form the final solution
This technique is widely used in computer science because it reduces complex problems into simpler forms.
1.2 General Strategy
A problem using Divide and Conquer follows three steps:
Step Description
Divide Break problem into subproblems of same type
Conquer Solve subproblems recursively
Combine Merge results of subproblems
1.3 Real-Life Analogy
Imagine sorting a big stack of books:
• You split books into smaller stacks
• Sort each stack separately
• Combine them into a sorted pile
This is exactly how Merge Sort works.
2. Recurrence Relation in Divide and Conquer
Most divide and conquer algorithms follow:
T(n) = aT(n/b) + f(n)
Variable Meaning
a Number of subproblems
n/b Size of each subproblem
f(n) Work done to divide + combine
DSA NOTES 1
, BSCS | DSA Notes Algorithms – Divide and Conquer
2.1 Master Theorem (Basic Idea)
Used to analyze time complexity:
• If dividing dominates → recursive cost dominates
• If merging dominates → combine cost dominates
Used to solve recurrence relations:
Case Condition Result
Case 1 f(n) = O(n^c), c < log_b(a) T(n) = O(n^log_b(a))
Case 2 c = log_b(a) T(n) = O(n^c * log n)
Case 3 c > log_b(a) T(n) = O(f(n))
3. Binary Search (Divide & Conquer Example)
3.1 Concept
Binary Search works on sorted arrays only. Steps:
1. Find middle element
2. If target = middle → found
3. If target < middle → search left half
4. Else → search right half
3.2 Time Complexity
O(log n)
3.3 C++ Program (Binary Search)
Question: Write a C++ program to implement Binary Search using an iterative
approach. The program should search a given key in a sorted array and return
its index if found, otherwise return -1.
#include <iostream>
using namespace std;
// Function to perform Binary Search
int binarySearch(int arr[], int left, int right, int key) {
// Loop tab tak chalega jab tak search space valid hai
while (left <= right) {
// Mid index calculate karna (overflow avoid karne ke liye)
int mid = left + (right - left) / 2;
// Agar mid element key ke equal hai → element mil gaya
DSA NOTES 2
DIVIDE AND CONQUER ALGORITHMS
Comprehensive Notes & Implementation Guide
Topic Algorithms Paradigm Divide & Conquer Focus C++ Implementation
1. Introduction to Divide and Conquer Algorithms
1.1 Definition
Divide and Conquer is a fundamental algorithm design paradigm in which a problem is:
1. Divided into smaller subproblems
2. Conquered by solving each subproblem recursively
3. Combined to form the final solution
This technique is widely used in computer science because it reduces complex problems into simpler forms.
1.2 General Strategy
A problem using Divide and Conquer follows three steps:
Step Description
Divide Break problem into subproblems of same type
Conquer Solve subproblems recursively
Combine Merge results of subproblems
1.3 Real-Life Analogy
Imagine sorting a big stack of books:
• You split books into smaller stacks
• Sort each stack separately
• Combine them into a sorted pile
This is exactly how Merge Sort works.
2. Recurrence Relation in Divide and Conquer
Most divide and conquer algorithms follow:
T(n) = aT(n/b) + f(n)
Variable Meaning
a Number of subproblems
n/b Size of each subproblem
f(n) Work done to divide + combine
DSA NOTES 1
, BSCS | DSA Notes Algorithms – Divide and Conquer
2.1 Master Theorem (Basic Idea)
Used to analyze time complexity:
• If dividing dominates → recursive cost dominates
• If merging dominates → combine cost dominates
Used to solve recurrence relations:
Case Condition Result
Case 1 f(n) = O(n^c), c < log_b(a) T(n) = O(n^log_b(a))
Case 2 c = log_b(a) T(n) = O(n^c * log n)
Case 3 c > log_b(a) T(n) = O(f(n))
3. Binary Search (Divide & Conquer Example)
3.1 Concept
Binary Search works on sorted arrays only. Steps:
1. Find middle element
2. If target = middle → found
3. If target < middle → search left half
4. Else → search right half
3.2 Time Complexity
O(log n)
3.3 C++ Program (Binary Search)
Question: Write a C++ program to implement Binary Search using an iterative
approach. The program should search a given key in a sorted array and return
its index if found, otherwise return -1.
#include <iostream>
using namespace std;
// Function to perform Binary Search
int binarySearch(int arr[], int left, int right, int key) {
// Loop tab tak chalega jab tak search space valid hai
while (left <= right) {
// Mid index calculate karna (overflow avoid karne ke liye)
int mid = left + (right - left) / 2;
// Agar mid element key ke equal hai → element mil gaya
DSA NOTES 2
