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
