Home arrow Development Cycles arrow Page 3 - Divide and Conquer Algorithm Technique
DEVELOPMENT CYCLES

Divide and Conquer Algorithm Technique


This is the second segment of the multi-part series covering various algorithm design paradigms. As the title suggests, today our job is to present, discuss, and learn as much as we can, as briefly and clearly possible, about the divide-and-conquer algorithm technique. It is definitely an important concept in computer science and should be ready to be pulled out of every coder’s toolbox.

Author Info:
By: Barzan "Tony" Antal
Rating: 5 stars5 stars5 stars5 stars5 stars / 20
September 23, 2008
TABLE OF CONTENTS:
  1. · Divide and Conquer Algorithm Technique
  2. · The Theory
  3. · Binary Searching Problem and Solution
  4. · Merge Sort Problem and Solution
  5. · Taking a Break

print this article
SEARCH DEVARTICLES

Divide and Conquer Algorithm Technique - Binary Searching Problem and Solution
(Page 3 of 5 )

We are going to present two outstandingly popular problems that are considered de facto standard prime examples for D&C algorithms in action. We are going to begin with the binary searching problem. The problem goes like this: we have a strictly increasing sequence of numbers (let be a[1 … n]). We are given a number for which we need to search in the sequence; if we find it, we return its position.

How do we approach this problem using what we have just learned about D&C? The most important criterion is that the given sequence of numbers is in increasing order. This means that if we target the middle element of the sequence, and consider this element as a point of reference, we can decide whether the element we are searching for is located in the first half or the second half of the sequence.

Intuitively it makes sense that by doing this we are half-way reducing the “work” that must be done, thus, increasing two-fold the algorithm’s efficiency compared to a naïve iterative approach (where we move through the entire sequence). However, let’s not forget that we do not split/divide only once. As soon as we’ve determined which half the element for which we're searching is located, we can yet again target that half’s middle element, consider it a point of reference, and decide (again) which half contains our number. 

Now if we do the above scenario on and on until the “half” that we get is nothing but one element, then either this is the element we want, or the specified element cannot be found. It's as simple as that. Check out the following pseudocode.

function binary_search (a[], x, i, j)

if i > j then

return NULL

else

k := (i + j) / 2

if x = a[k] then

return k

else

if x < a[k] then

return binary_search (a, x, i, k-1)

else

return binary_search (a, x, k+1, j)

end if

end if

end if

end function

Let’s see it written in ANSI C. We call the following function using the following line of code: result = binary_search(a, x, 0, n); then interpret the result variable.

int binary_search(int *a, int x, int i, int j)

{

if (i > j)

return 0; // not found in the entire sequence

else

{

int k = (i + j) / 2; // middle element

if (x == a[k]) // if found

return k; // return the position

else // not found –YET-

{

if (x < a[k]) // divide; first half of the sequence

return binary_search(a, x, i, k-1);

else // divide; second half of the sequence

return binary_search(a, x, k+1, j);

}

}

}

If you want to download the source code of a program that implements the above code snippet, then click on the Download button below.


blog comments powered by Disqus
DEVELOPMENT CYCLES ARTICLES

- Division of Large Numbers
- Branch and Bound Algorithm Technique
- Dynamic Programming Algorithm Technique
- Genetic Algorithm Techniques
- Greedy Strategy as an Algorithm Technique
- Divide and Conquer Algorithm Technique
- The Backtracking Algorithm Technique
- More Pattern Matching Algorithms: B-M
- Pattern Matching Algorithms Demystified: KMP
- Coding Standards
- A Peek into the Future: Transactional Memory
- Learning About the Graph Construct using Gam...
- Learning About the Graph Construct using Gam...
- Learning About the Graph Construct using Gam...
- How to Strike a Match

Watch our Tech Videos 
Dev Articles Forums 
 RSS  Articles
 RSS  Forums
 RSS  All Feeds
Write For Us 
Weekly Newsletter
 
Developer Updates  
Free Website Content 
Contact Us 
Site Map 
Privacy Policy 
Support 

Developer Shed Affiliates

 




© 2003-2017 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap
Popular Web Development Topics
All Web Development Tutorials