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