C语言——二分查找【简单理解版】

发布时间:2024年01月06日

C语言——二分查找【简单理解版】

前言

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,就代表没有找到。

好了,今天就到这儿,喜欢就点个关注吧!

文章来源:https://blog.csdn.net/2301_80309505/article/details/135321502
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。