C语言函数二分查找(折半查找)

C语言函数二分查找(折半查找)

参考视频讲解哔哩哔哩比特鹏哥的视频 ——链接

二分查找
#include <stdio.h>

	//二分查找
   //在一个有序数组中查找具体的某个数
	//如果找到了返回，这个数的下标，找不到返回-1

	//例如我要在这个数组中找到7
	//首先找到这组被查找元素的中间的元素
	//假如说发现中间元素5要比我要找的数要小
	//说明我要找的数在5的右边，这样我的范围就缩小了一半
	//查找了一次范围就缩小了一半，这样的速度是比较快的
	//这就叫二分查找(折半查找)
	//那么怎么找到中间元素的下标呢
	//原来的数组是1 2 3 4 5 6 7 8 9 10 
	//他们的下标是0 1 2 3 4 5 6 7 8 9
	//左下标为0，右下标为9
	//给定完这组元素的下标，就可以通过左右元素的下标来确定中间元素的下标
	//就是这组被查找元素的左下标是0，右下标是9
	//0和9的平均值是4，下标4锁定的元素是5，就可以认为5就是这组元素的中间元素了
	//5这个元素比我要找的7要小
	//说明我要被查找的元素范围就变成了6到10
	//新的范围，左下标是5，右下标是9
	//左右下标又可以求出一个平均值是7，又找到一个对应的元素是8
	//所以这一组查找范围的中间元素是8
	//用8再跟我要找的元素比一下，比我找的元素要大
	//说明我要查找的元素在8的左边
	//这时候要查找的范围被再次的缩小成了6到7


	//基本思想，当我确定了被查找范围时候，要确定他的左下标和右下标，然后求出下标的平均值，
	//找到中间元素，将中间元素和我要找的元素比一下，如果比我找的元素大，说明我要找的元素在他的左边，
	//如果比我要找的元素小，说明我要找的元素在他的右边，
	//这样确定出新的范围，出现新的左右下标。
	//一直找到左右下标无法确定新的范围，他们之间没有元素可以被查找的时候，结束，说明没有找到
	//如果在某一次查找的时候，找到了，下标相等了，说明找到了，把下标给过来

int number_search(int arr[], int k)
{
	//算法实现
	int sz = sizeof(arr) / sizeof(arr[0]);
	int left = 0;//左下标
	int right = sz - 1 ;//右下标
	//放到循环中
	while (left <= right)//这样才说明中间是有元素可以被查找的
	{
		int mid = (right + left) / 2;//中间元素的下标
		//拿到这个mid——锁定个元素
		if (arr[mid] < k)//如果中间元素比我要找的k要小，
						//被查找范围的右下标不用变，左下标变成mid+！
		{
			left = mid + 1;
		}
		else if (arr[mid] > k)
		{
			right = mid - 1;
		}
		else
		{
			return mid;
		}
		//如果找不到
		return -1;//返回去了
	}
}


int main(void)
{
	
	int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
	int k = 7;
	int ret = number_search(arr, k);
	if (ret == -1)
	{
		printf("找不到指定的数字\n");
	}
	else
	{
		printf("找到了，下标是：%d\n",ret);
	}
	return 0;
}

//运行发现找不到结果——代码出现了问题
//自己找问题的方法

//部分位置添加注释后
 二分查找
#include <stdio.h>

int number_search(int arr[], int k)
//实际上这地方传递过来的数组arr是首元素地址
//本质上这里的arr是个指针，因为指针才可以接收地址
{
	//算法实现
	int sz = sizeof(arr) / sizeof(arr[0]);
	// 4/4=1  无法得到元素个数
	//sz出现了问题
	int left = 0;//左下标
	int right = sz - 1;//右下标
	//放到循环中
	while (left <= right)//这样才说明中间是有元素可以被查找的
	{
		int mid = (right + left) / 2;//中间元素的下标
		//拿到这个mid——锁定个元素
		if (arr[mid] < k)//如果中间元素比我要找的k要小，
						//被查找范围的右下标不用变，左下标变成mid+！
		{
			left = mid + 1;
		}
		else if (arr[mid] > k)
		{
			right = mid - 1;
		}
		else
		{
			return mid;
		}
		//如果找不到
		return -1;//返回去了
	}
}


int main(void)
{

	int arr[] = {1,2,3,4,5,6,7,8,9,10};
	int k = 7;
	//只要把数组传参传过去
	//在内部是不能再上面的方式求元素个数了
	//数组是一块连续的空间，他里面可以放很多个元素
	//数组在传参的时候
	int ret = number_search(arr, k);//在这里仅仅传的是数组第一个元素的地址，不是所有元素
	if (ret == -1)
	{
		printf("找不到指定的数字\n");
	}
	else
	{
		printf("找到了，下标是：%d\n", ret);
	}
	return 0;
}

既然传进去不行，那就在外面算，

//修改版(注释已经删除)(只有修改后的注释)
二分查找
#include <stdio.h>
//将多传递过来的参数sz接收
int number_search(int arr[], int k,int sz)
{
	int left = 0;
	int right = sz - 1 ;	
    //进入到这个循环中就是一次二分查找
    //在这里要进行很多次
    //每一次二分查找的第一步是找被查找范围的中间元素的下标
	while (left <= right)
	{
		int mid = (right + left) / 2;
		if (arr[mid] < k)
		{
			left = mid + 1;
		}
		else if (arr[mid] > k)
		{
			right = mid - 1;
		}
		else
		{
			return mid;
		}
	}
    return -1;
}
int main(void)
{	
	int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
	int k = 7;
    //将计算元素个个数
    int sz = sizeof(arr) / sizeof(arr[0]);
	int ret = number_search(arr, k,sz);//将sz也传过去
	if (ret == -1)
	{
		printf("找不到指定的数字\n");
	}
	else
	{
		printf("找到了，下标是：%d\n",ret);
	}
	return 0;
}

正在学习ing