目录
一、算法思想
二、完整代码+注释
三、思路剖析
四、结语
一、算法思想
折半查找也叫二分查找,首先计算数组中间的位置(元素个数除以2),将数组中间位置处的下标与查找的元素进行比较,如果相等,则查找成功;否则利用中间位置将数组分为左、右两个部分,如果中间位置的下标大于查找的元素,则查找左子表,否则查找右子表。
重复上面的过程,直到找到要查找的关元素为止,否则查找失败不存在此元素。
二、完整代码+注释
#include
int binary_search(int arr[], int k, int sz)
{
int left = 0;//左下标
int right = sz - 1;//右下标
while (left <= right)//左下标<=右下标说明中间还有元素要查找
{ //中间元素的下标
int mid = (left + right) / 2;//mid就是折半之后的数组元素个数
//mid-1和mid+1逐渐接近要找的元素
if (arr[mid] > k)//mid数组的下标大于k说明要找的元素在数组的左边
{
right = mid - 1;//mid-1赋给右边的左边
}
else if (arr[mid] < k)//mid数组的下标小于k说明要找的元素在数组的右边
{
left = mid + 1;//mid+1赋给左边的下标
}
else
{
return mid;//返回找到的下标
}
}
return -1;//整个数组都查找了一遍,没有要找到要找的元素就返回-1
}
int main()
{
int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
int k = 7;//要找的元素,找到后输出它的下标
//数组的个数=数组的总大小/数组一个元素的大小
int sz = sizeof(arr) / sizeof(arr[0]);//sz就是数组元素的个数
int ret = binary_search(arr, k, sz);
if (-1 == ret)//ret等于接收的-1说明整个数组没有要找的元素
{
printf("找不到了\n");
}
//ret不等于接收的-1就说明找到了
else
{
printf("找到了,下标是:%d\n", ret);//输出找到的元素下标
}
return 0;
}
三、思路剖析
mid小于要找的元素情况
mid大于要找的元素情况
你学废了吗?
四、结语
这是关于如何用C语言实现二分查找的教程,希望能对大家有所帮助。
如果对我的文章有什么建议或问题可以在评论区留言。
原创不易,还请三连。
你们的点赞、收藏和关注是对我最大的鼓励。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)