bsearch_recursion.cpp

来自「设计模式：工厂模式、单例模式的基本实现」· C++ 代码 · 共 93 行

/************************************
* Copyright (c) 2008,LDCI
*
* 文件名称： BSearch_Recursion.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 :	查找关键字
*		_nLow : 查找范围下界
*		_nHigh : 查找范围上界
* 返回值:	查找结果，-1表示查找失败，否则为查找到的元素下标
* 功能:
*		对顺序存储结构的线性表进行递归二分查找
* 作者:		左建华
* 编写明细:
*		2008-05-29	Created		左建华
*	
**************************************************/
int BSearch(SeqList* _pList, DataType _key, int _nLow, int _nHigh)
{	
	if( _nLow>_nHigh )
	{
		 return -1;	
	}
	else
	{
		int nMiddle = (_nLow+_nHigh)/2;
		
		if( _pList->data[nMiddle] == _key )
		{
			return nMiddle;
		}
		else if( _pList->data[nMiddle] > _key )
		{
			BSearch( _pList, _key, _nLow, nMiddle-1 );
		}
		else
		{
			BSearch( _pList, _key, nMiddle+1, _nHigh );
		}
	}
}

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, 122, 0, pList->nLength-1);
	printf("nFindIndex = %d\n", nFindIndex);

	free(pList);

	return 0;
}