Page 263 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures

Notes
Did u know? This is an expensive operation as it requires, in worst case, log comparisons
n
2
and n item moves.
The binary search assumes easy random-access to the data space it is searching. An array is the
data structure that is most often used because it is easy to jump from one index to another in an
array. It is difficult, on the other hand, to efficiently compute the midpoint of a linked list and
then traverse there inexpensively. The binary search tree data structure and algorithm attempt
to solve these array-based binary search weaknesses.

Example: Below is an iterative implementation of the binary search in C. The binary
search algorithm can be implemented as a recursive algorithm also.

In this program, we search for the target value in an array. Return the index on success and
NOTFOUND, or -1, on failure.
#include “global.h”
#include “debug.h”
typedef int KEY;
#define NOTFOUND -1
extern int NumElements(KEY *x); // to return the # of elements in an
array

DWORD bsearch(KEY kTarget, KEY *pkSearchspace)
{

BOOL fFound = NO; // have we found it yet?
DWORD dwFirst = 0; // search space starts at index zero
DWORD dwLast = NumElements(searchspace); // # of elements in
search space
DWORD dwMidpoint; // current midpoint
// Check return value of NumElements and make precondition
assertions
ASSERT(dwLast >= dwFirst);
ASSERT(pkSearchspace);
// iterative implementation — could also be done recursively
while ((dwFirst <= dwLast) && (!fFound))
{
// calculate the dwMidpoint of the current [sub]range
dwMidpoint = (dwFirst + dwLast) / 2;
// compare the target with the value of dwMidpoint element
if (pkSearchspace[dwMidpoint] == kTarget)
{
fFound = YES;
}
else

256 LOVELY PROFESSIONAL UNIVERSITY