LuckyHu Blog

Home MyGame MyApp About

二分查找 以及sizeof

02 Sep 2012

Talk is cheap.

#include <stdio.h>

int binary_search(int array[],int lenth,int k);

int main(void){
	
	int array[]={1,3,9,12,34,88,89,127,298,333,356,444,516,728,829,918,1029};
	int k = 728;

	printf("start search \n");

	int lenth = sizeof(array)/sizeof(*array); 

	int index = binary_search(array,lenth,k);

	if(index<0)
		printf("not find\n");
	else
		printf("find the number %d,the index is %d\n",k,index);

	return 0;
}

int binary_search(int array[],int lenth,int k){

	int low=0,high=lenth -1;

	while(low<=high){
		
		int mid = (low + high) / 2;
		//int mid = low + (high - low)/2;

		if(k<array[mid])
			high = mid-1;
		else if(k>array[mid])
			low =mid+1;
		else
			return mid;

	}

	return -1;
}

打算以后逐步把一些基本算法还是动手写写,也算是弥补下非科班出身的不足。关于其中的一行://int mid = low + (high - low)/2,为了防止溢出,可以写成这样的写法。

关于C语言 sizeof函数 函数的参数传递

c语言中关于数组的长度并没有现成的api,我看网上说的一般求法是就是我在代码中写的那种,通过sizeof函数来求,开始的时候我还犯了个错误,我把binary_search函数的传入写成了 (int array[],int k),也就是说我并没有说明数组长度,这在Java中是很平常的事情,因为数组的长度信息已经包含在了数组对象中,我以前看到c中的这种写法的时候还不是很理解,现在终于明白了。

错误就发生在我在binary_search中使用了两个sizeof来求数组的长度,但求得长度始终都是2,在参数定义中看起来传过来的是一个int array[],c语言是允许这么写的,但你实际得到的是一个int指针,当你调用sizeof的时候,实际上是求这个指针地址的字节长度,我这台机器是64位机,那么地址长度就是8字节,一个int的长度是4字节,所以我总得到数组长度是2.

所以虽然说数组和指针基本上可以理解为一个东西,但实际上在某些情况下还是有区别的。