Hello,亲爱的小伙伴们,我是莹莹,今天我给大家分享关于二分查找的知识。
学会二分查找,将可以快速解决生活中找有序数字的问题,话不多说,我们开始吧!
如果我们写代码时,发现一组数组是有序的,我们要找其中一个数字,使用二分查找是非常快的。
二分查找的前提:有序
二分查找的基本原理是将目标值与数组中间位置的元素进行比较。如果目标值小于中间位置的元素,则在数组的左半部分继续查找;如果目标值大于中间位置的元素,则在数组的右半部分继续查找。通过不断缩小查找范围,最终可以找到目标值在数组中的位置。
以下是不用二分查找写出来的代码
//找1~10中的数字,例如:找7
#include<stdio.h>
int main()
{
int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
int i = 0;
int sz = sizeof(arr) / sizeof(arr[0]);
int find = 0;
int k = 7;
for (i = 0; i < sz; i++)
{
if (k == arr[i])
{
find = 1;
printf("找到了,下标是%d\n", i);
break;
}
}
if (find == 0)
{
printf("没找到");
}
return 0;
这种方法只适合于一些较小的数,如若是非常庞大的数字系统,一个一个的找是非常麻烦的。
使用二分查找的方法:
#include<stdio.h>
int main()
{
int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
int k = 2;
int sz = sizeof(arr) / sizeof(arr[0]);
int left = 0;
int right = sz - 1;
int find = 0;
while (left <= right)
{
int mid = (left + right) / 2;
if (arr[mid] < k)
{
left = mid + 1;
}
else if (arr[mid] > k)
{
right = mid - 1;
}
else
{
find = 1;
printf("找到了,下标是%d\n", mid);
break;
}
}
if (find == 0)
printf("找不到了,我哭了");
return 0;
}
//此代码注意打大括号,if,else if语句等等,他们都只能带一条独立的语句,如果要带多条的话,注意打大括号。
//解析://二分查找
//计算中间元素的下标
//int left = 0;
//int right = sz - 1;//sz:元素的个数:int sz = sizeof(arr) / sizeof(arr[0]);
//中间元素的下标:int mid = (left + right) / 2;
//二分查找的过程中,每检索一次,左下标或者右下标都会向中间移动,建议代入具体值仔细体会。
//代码如下:
//if (arr[mid] < k)
//{
// left = mid + 1;
//}
//else if (arr[mid] > k)
//{
// right = mid - 1;
//}
//else
//{
// printf("找到了,下标是%d\n", mid);
// break;
//}
//使用循环while
//但是while的条件是什么呢?
//left <= right
//只要是left <= right,就说明中间还有元素能够查找,那么它就会一次又一次的循环,直到找到正确数据。
//任何查找都分为找得到和找不到(压根就没有这个数)两种情况,可以设置一个变量find,如果find = 1,代表找到了,如果find = 0,就代表没有找到。
好了,今天就到这儿,喜欢就点个关注吧!