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.
Next: Merge Sort Problem and Solution >>
More Development Cycles Articles
More By Barzan "Tony" Antal
/ 4 
