Divide and Conquer Technique - Binary Search, Quick Sort, Merge Sort

 

UNIT II - DIVIDE AND CONQUER TECHNIQUE

General Method – Binary Search – Merge Sort – Quick Sort. 

GENERAL METHOD

The divide and conquer technique is a problem-solving approach that works in three main steps:

1.      Divide: Break down a large problem into smaller, simpler sub-problems.

2.     Conquer: Solve each of the sub-problems individually. This can often be done recursively if the sub-problems are still large.

3.   Combine: Combine the solutions of the sub-problems to get the solution to the original, larger problem.

This approach is commonly used in algorithms like binary search, merge sort and quick sort, where breaking down a problem makes it easier and faster to solve.

 

BINARY SEARCH

Binary search is an efficient algorithm for finding a target value within a sorted list. Here’s how it works:

1. Start in the Middle: Look at the middle element of the list.
2. Compare:
• If the middle element is the target, you’re done!
• If the target is less than the middle element, repeat the search on the left half.
• If the target is greater than the middle element, repeat the search on the right half.
3. Repeat: Continue dividing the search area in half until you find the target or narrow it down to zero elements.

Because it halves the search space each step, binary search is very fast, with a time complexity of O(logn), but it only works on sorted lists

 Example:

MERGE SORT

Merge sort is a sorting algorithm that works by splitting a list into smaller parts, sorting those parts, and then merging them back together in order. Here’s a step-by-step breakdown:

1.   Divide: Split the list into two halves. Keep splitting each half until every part has only one element (a single-element list is already sorted).

2.    Conquer: Recursively sort each half (although they’re already split down to single elements, so this step is trivial).

3.  Merge: Combine (merge) each pair of sorted lists back together in sorted order. Continue merging pairs until there’s only one sorted list left.

The main advantage of merge sort is its consistent performance, with a time complexity of O(nlogn), making it efficient for large lists.

Example:

 

QUICK SORT

Quick sort is a popular sorting algorithm that sorts items by repeatedly dividing the list into smaller parts. Here’s how it works, step-by-step:

1.   Pick a Pivot: Choose a value from the list, called the "pivot." This can be any element, but typically the middle or last element is chosen.

2.   Partition: Rearrange the list so that all elements less than the pivot are on one side, and all elements greater are on the other side.

3.   Recursively Sort: Apply the same process (choose a pivot and partition) on the smaller lists created on either side of the pivot.

4.   Combine: Since each smaller list is now sorted, combining them produces the fully sorted list.

Quick sort is efficient, with an average time complexity of O(nlogn), making it faster than many other sorting algorithms for large lists.

Example: