【C语言】调用函数进行数组内元素的二分查找

在遇到很大的数据时,我们想找一个到其中一个元素,遍历是一种低效的方法,这时用二分折中来查找就会提高很大的效率。

我们比如说想在10中找其中一个元素7,有这么几个步骤:

1.首先你要求出你这些元素的总个数,用可以sizeof来求,sizeof(总大小)/sizeof(第一个元素的大小)

2.定义一个变量来表示第一个元素和最后一个元素

3.加起来相除得到中间数

4.用想查找的元素与中间数作比较,如果是>则把第一个元素赋给中间值+1,如果是<则把最后一个元素赋给中间值-1。从而缩小查找范围,循环判断,进而找到所要查找的元素,返回它的下标

int binary_search(int a[],int k,int s)//返回类型 int ,由实参传递到形参
{
	int left = 0;//左边第一个下标
	int right = s-1;//右边的下标
	while (left<=right)//正常情况下都是left<right,如果left=right的时候可能就是找到了
	{
		int mid = (left + right) / 2;//二分
		if (a[mid] > k)//如果要查找的数组a中的mid大于k,就说明中间值比k大,那右边的直接可以舍弃,跳到中间值,并减一位
		{
			right = mid - 1;
		}
		else if (a[mid] < k)
		{
			left = mid + 1;
		}
		else//大于小于都找完了,剩下就是等于了 这时候返回中间值mid就是所要查找的值了
		{
			return mid;
		}
	
	}
	return -1;//如果都没有满足上面的条件 就是找不到 返回-1
}

int main()   //创建函数二分查找
{
	int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
	int key = 7;
	int sz = sizeof(arr) / sizeof(arr[0]);//40个byte除以4个字节 就是10 ——>10个元素

	//找到了返回下标 ;找不到返回-1 (不返回0是因为第一个元素的下标也是0 容易歧义
	int ret = binary_search(arr,key,sz);//实参传递:数组、要查找的值、元素个数
 //数组arr传参,实际传递的不是数组本身,而是数组的首位元素的地址
	if (-1 == ret)
		printf("没找到\n");
	else
		printf("找到了,下标是:%d\n",ret);
	return 0;
}

上一篇:浅析数据类型


下一篇:嵌入式linux学习笔记---TCP立即发出 以及 TCP的keep alive