13-08-2012, 02:25 PM
Divide And Conquer Strategy:
Lec2_Divide&Conquer.pdf (Size: 687.45 KB / Downloads: 68)
Divide-and-Conquer
Divide-and-Conquer Strategy: Is a Top Down Approach i.e. the solution to atop level instance of a problem is obtained by going down and obtaining solutions to smaller instances.
Divide a problem into smaller pieces
Instances of the same type of problem
Solve recursively
Obtain solution by combining result
Binary Search:
A binary searchassumes the list of items in the search pool is sorted
It eliminates a large part of the search pool with a single comparison
A binary search first examines the middle element of the list --if it matches the target, the search is over
If it doesn't, only one half of the remaining elements need be searched