UNIT - III
Divide and Conquer Method-Introduction-Binary Search-Finding Min Max-Maximum
Subarray Problem-Towers of Hanoi Problem-Finding the kth element-Analysis of
Quick and Merge Sort.
DIVIDE AND CONQUER METHODOLOGY
A divide and conquer algorithm work by recursively breaking down a problem into
two or more sub-problems of the same (or related) type (divide), until these become simple
enough to be solved directly (conquer).
Divide-and-conquer algorithms work according to the following general plan:
1. A problem is divided into several subproblems of the same type, ideally of about equal
size.
2. The subproblems are solved (typically recursively, though sometimes a different algorithm
is employed, especially when subproblems become small enough).
3. If necessary, the solutions to the subproblems are combined to get a solution to the original
problem.
The divide-and-conquer technique as shown above, depicts the case of dividing a problem
into two smaller subproblems, then the subproblems solved separately. Finally, solution to the
original problem is done by combining the solutions of subproblems.
[Link] SEARCH
A binary search is efficient algorithm to find the position of a target (key) value within a
sorted array.
The binary search algorithm begins by comparing the target value to the value of the
middle element of the sorted array. If the target value is equal to the middle element's value,
then the position is returned and the search is finished.
If the target value is less than the middle element's value, then the search continues on the
lower half of the array.
If the target value is greater than the middle element's value, then the search continues on
the upper half of the array.
This process continues, eliminating half of the elements, and comparing the target value to
the value of the middle element of the remaining elements - until the target value is either
found (position is returned).
Binary search is a remarkably efficient algorithm for searching in a sorted array (Say
A). It works by comparing a search key K with the array’s middle element A[m]. If they
match, the algorithm stops; otherwise, the same operation is repeated recursively for the
first half of the array if K <A[m], and for the second half if K >A[m]:
Though binary search is clearly based on a recursive idea, it can be easily
implemented as a non-recursive algorithm, too. Here is pseudocode of this non-recursive
version.
The standard way to analyze the efficiency of binary search is to count the number of
times the search key is compared with an element of the array (three-way comparisons). One
comparison of K with A[m], the algorithm can determine whether K is smaller, equal to, or
larger than A[m].
As an example, let us apply binary search to searching for K = 70 in the array. The iterations
of the algorithm are given in the following table:
The worst-case inputs include all arrays that do not contain a given search key, as well as
some successful searches. Since after one comparison the algorithm faces the same situation
but for an array half the size,
▪ First, The worst-case time efficiency of binary search is in Θ(log n).
▪ Second, the algorithm simply reduces the size of the remaining array by half on each
▪ iteration, the number of such iterations needed to reduce the initial size n to the final
size 1 has to be about log2 n.
▪ Third, the logarithmic function grows so slowly that its values remain small even for
very large values of n.
▪ The average case slightly smaller than that in the worst case Cavg(n) ≈ log2 n
▪ The average number of comparisons in a successful is Cavg(n) ≈ log2 n − 1
▪ The average number of comparisons in an unsuccessful is Cavg(n) ≈ log2(n + 1).
(ii)Maximum Sum Subarray Problem
Find the kth smallest element in an unsorted array
The Divide and Conquer approach can be used to find the kth smallest element in an
unsorted array efficiently. This method is commonly known as the QuickSelect algorithm. It
is similar to the QuickSort algorithm but instead of sorting the entire array, it partially sorts
the array to find the kth smallest element.
Here's the basic idea:
1. Choose a Pivot: Like QuickSort, pick a pivot element from the array.
2. Partition the Array: Partition the array into two parts: elements less than the pivot
and elements greater than or equal to the pivot.
3. Recur in One Half:
a. If p == k, the pivot is the kth smallest element.
b. If p > k, the kth smallest element lies in the left half (since all smaller elements
are there). We recur only on the left part of the array.
c. If p < k, the kth smallest element lies in the right half (since the required
element is greater than the pivot). We recur on the right part of the array.
The QuickSelect algorithm has an average time complexity of O(n), although the worst case
can be O(n²) if poor pivot choices are made.
Algorithm:
Algorithm quickselect(arr, low, high, k)
{
if (low <= high) then
pi = partition(arr, low, high)
if (pi == k) then
return arr[pi]
else if ( pi > k)
return quickselect(arr, low, pi - 1, k)
else:
return quickselect(arr, pi + 1, high, k)
}
Algorithm partition(arr, low, high){
{
pivot = arr[low]
i = low , j = high + 1
repeat
repeat i = i+1 until arr[i] >= pivot
repeat j = j -1 until arr[j] <= pivot
swap(arr[i],arr[j])
until I <= j
swap(arr[i],arr[j])
return j
}
Example:
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner