bsearch_norecursion.cpp

设计模式：工厂模式、单例模式的基本实现

/************************************
* Copyright (c) 2008,LDCI
*
* 文件名称： BSearch_NoRecursion.cpp
* 摘要：
*		使用 C 语言实现对顺序存储结构的线性表进行非递归二分查找
************************************/
#include <stdio.h>
#include <stdlib.h>


#define LISTSIZE 100			// 表的长度，根据实际情况而定
typedef int DataType;			// 数据，根据实际情况而定
typedef struct
{
	DataType data[LISTSIZE];	// 存放所有数据的空间
	int nLength;				// 当前表的长度
}SeqList;

void Show(SeqList* _pList)
{
	for(int i=0; i<_pList->nLength; i++)
	{
		printf("%d, ", _pList->data[i]);
	}
	printf("\n");
}

/**************************************************
* 函数名:	BSearch
* 参数:
*	形参:
*		_pList : 顺序存储结构的线性表
*		_key :	查找关键字
* 返回值:	查找结果，-1表示查找失败，否则为查找到的元素下标
* 功能:
*		对顺序存储结构的线性表进行非递归二分查找
* 作者:		左建华
* 编写明细:
*		2008-05-29	Created		左建华
*	
**************************************************/
int BSearch(SeqList* _pList, DataType _key)
{	
	int nLow = 0;
	int nHigh = _pList->nLength-1;
	int nMiddle = 0;

	while( nLow<=nHigh )
	{
		nMiddle = (nLow+nHigh)/2;

		if( _pList->data[nMiddle] == _key )
		{
			return nMiddle;
		}
		else if( _pList->data[nMiddle] < _key )
		{
			nLow = nMiddle+1;
		}
		else
		{
			nHigh = nMiddle-1;
		}
	}
	return -1;
}

int main(int argc, char** argv)
{	
	SeqList* pList = (SeqList*)malloc(sizeof(SeqList));

	pList->nLength = 8;

	pList->data[0] = 10;
	pList->data[1] = 11;
	pList->data[2] = 19;
	pList->data[3] = 21;
	pList->data[4] = 22;
	pList->data[5] = 30;
	pList->data[6] = 32;
	pList->data[7] = 122;

	Show(pList);

	int nFindIndex = BSearch(pList, 10);
	printf("nFindIndex = %d\n", nFindIndex);

	free(pList);

	return 0;
}