【C语言】二分查找(详解)
2023-12-15 13:38:39
🎥?岁月失语唯石能言的个人主页? ? ? ??
🔥个人栏专:秒懂C语言
?若在许我少年时,一两黄金一两风? ??
一、二分查找的思路?
? ? ? ?二分查找是一种高效的查找算法,尤其适用于有序数组。它的基本思想是通过将查找区间逐步缩小一半,从而快速定位目标元素。对于大型数据集,二分查找的效率远高于线性查找。然而,它要求数据必须有序,且实现相对复杂一些。总的来说,二分查找是一种非常实用和强大的工具,在许多场景下都能发挥出其独特的优势。
? ?举个例子:
????????朋友让你猜他刚买的一件衣服的价格,告诉你在(0~100)元之间。
????????我们一般都是先猜中间价位50元,他说猜低了,你再猜75元,这样一步步的缩减范围。直到锁定86元。你只要用几次二分查找就能找到价格。而你要是从一开始猜你得猜86次,速度和效率提升非常大。
二、思路分析
例子:????????int arr[] = {1,2,3,4,5,6,7,8,9,10};
首先题目会给你一个有序数组,让你找出某个数字比如说7的下标.
2.1定义变量
- 首先我们定义lift,right,key,mid四个变量。left的下标为0;right的下标用sizeof(arr)/sizeof(arr[0])-1? ?(整个数组的大小)/(一个数组元素的大小)-1? ?因为数组的下标是从0开始所以要减1。
- mid = (left + right) / 2;
如果left和right比较大的时候可能会越界,这时候可以改良一下:
-
mid = left+(right-left)/2;
2.2逻辑分析
- 然后我们需要拿arr[mid](50元)与key去比较大小然后不断缩小范围。
- 如果arr[mid] == key,那就说明找到了,直接打印。
- 如果arr[mid] > key说明你猜大了那你就要缩小范围1~100就要改成1~49(因为50比价格贵不需要取50元)所以right下标就要改成mid-1
- 同理,如果arr[mid] < key说明你猜小了那你就要缩小范围1~100就要改成51~100,left的下标改成mid+1
- 当然有人会担心mid = (left + right) / 2中(left + right)是奇数除出来不是整数怎么办。/ 符号位会自动舍掉余数不用当心。
if (arr[mid] == key)
{
printf("找到了,下标是%d\n", mid);
break;
}
if (arr[mid] > key)
{
right = mid - 1;
}
if (arr[mid] < key)
{
left = mid + 1;
}
- 然后在使用while循环来实现不断猜数字的过程
- while的条件就设置成left <= right,只要范围内还有数字就继续排查直到找出,例如3~5,直到找到只剩5~5,找到5。
- 或者全都找完了还找不到,这时候left和right会继续加减。这时left 就会大于?right,就打印找不到。
while (left <= right)
{
mid = (left + right) / 2;
if (arr[mid] == key)
{
printf("找到了,下标是%d\n", mid);
break;
}
if (arr[mid] > key)
{
right = mid - 1;
}
if (arr[mid] < key)
{
left = mid + 1;
}
}
if (left > right)
printf("找不到\n");
return 0;
同理,如果是降序数组的话只需要把?right = mid - 1;和 left = mid + 1;交换位置就行:
三、代码实现
这是升序的代码:
#include <stdio.h>
int main()
{
int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
int left = 0;
int right = sizeof(arr) / sizeof(arr[0]) - 1;
int key = 7;//要找的数字
int mid = 0;//记录中间元素的下标
while (left <= right)
{
mid = (left + right) / 2;
if (arr[mid] == key)
{
printf("找到了,下标是%d\n", mid);
break;
}
if (arr[mid] > key)
{
right = mid - 1;
}
if (arr[mid] < key)
{
left = mid + 1;
}
}
if (left > right)
printf("找不到\n");
return 0;
}
这是降序代码:
#include <stdio.h>
int main()
{
int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
int left = 0;
int right = sizeof(arr) / sizeof(arr[0]) - 1;
int key = 7;//要找的数字
int mid = 0;//记录中间元素的下标
while (left <= right)
{
mid = (left + right) / 2;
if (arr[mid] == key)
{
printf("找到了,下标是%d\n", mid);
break;
}
if (arr[mid] > key)
{
left = mid + 1;
}
if (arr[mid] < key)
{
right = mid - 1;
}
}
if (left > right)
printf("找不到\n");
return 0;
}
往期文章推荐:
C语言如何生成随机数以及设置随机数的范围。(超详细):http://t.csdnimg.cn/62LIP
【C语言】函数调用及创建,并将数组传参到函数:http://t.csdnimg.cn/cU9Ku
【C语言】——函数递归,用递归简化并实现复杂问题:http://t.csdnimg.cn/nsS4d
总结
以上就是关于二分查找的相关知识,二分查找虽然性能比较优秀,但应用场景也比较有限,底层必须依赖数组,并且还要求数据是有序的。所以我们在选用算法时需要从多方面考虑。
文章来源:https://blog.csdn.net/cz382487322/article/details/134934729
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!