|
Below is an iterative implementation of the binary search in C. The
binary search algorithm can be implemented as a recursive algorithm
also.
//+----------------------------------------------------------------------------
//
// File: binsearch.c
//
// Module: Binary Search Example
//
// Synopsis: Sample binary search code.
//
// Author: sgasch
//
// Created 28 May 1999
//
//+----------------------------------------------------------------------------
#include
#include
#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
//+----------------------------------------------------------------------------
//
// Function: bsearch
//
// Synopsis: Search for the target value in an array. Return the
// index on success and NOTFOUND, or -1, on failure.
//
// Arguments: KEY kTarget - target value
// KEY *pkSearchspace - pointer to the search space
//
// Returns: DWORD
//
// History: sgasch Created Header 28 May 1999
//
//+----------------------------------------------------------------------------
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
{
//
// if the dwMidpoint is not the target adjust the range accordingly
//
if (target < searchspace[dwMidpoint])
{
dwLast = dwMidpoint - 1;
}
else
{
dwFirst = dwMidpoint + 1;
}
}
//
// Return value
//
if (fFound)
{
return(dwMidpoint);
}
else
{
return(NOTFOUND);
}
}
}
|
Search