二元搜索代码,C代码库,德仔网

代码语言

代码分类

【C】二元搜索

作者:茶壶 / 发布于2015/6/29/ 801


	//============================================================================
	// Function:二元搜索算法
	// worst case:W(N)=lg(N+1)/lg(2)
	// average case:A(N)=(k*2^(k+1)-2^k+1)/(2^(k+1)-1),where k=lg(N+1)/lg(2) 假设有N种可能在list中，有N+1中可能不在list中时。
	// In &mdash;&mdash;待搜索数组 list（类型 int*）。
	// 目标值 target（类型 int）；
	// 待搜索数组长度 n（类型 int）
	// Out&mdash;&mdash;无
	// return:目标位置 middle（类型 int，0为起始位置，n为未找到）。
	// note:数组list必须是从小到大排列的有序数组
	// bug:n可以小于list已分配长度，如果n大于list已分配长度，则可能发生内存溢出
	//============================================================================
	int BinarySearch(int *list,int target,int n)
	{
	 int middle;
	 int start=1;
	 int end=n;
	 while(start<=end){
	 middle=(start+end)/2;
	 if(list[middle]==target){
	 return middle;
	 }
	 else if(list[middle]<target){
	 start=middle+1;
	 }
	 else{
	 end=middle-1;
	 }
	 }
	 return n;
	}

试试其它关键字

　二元　　搜索　

同语言下

可能有用的

茶壶贡献的其它代码(9)