C语言之二分查找网站首页 技术杂谈

C语言之二分查找

北飞的山羊 2023-06-04 04:00:02

简介C语言之二分查找

一、二分查找算法

二、分支语句中应注意的小点

一、二分查找算法

所谓二分查找，就是要在一组有序的数列中，查找给定的数是否在此数列中。

最主要的步骤有三个：

1.确定被查找的范围的左右下标left、right
2.根据left和right，确定中间元素的下标mid
3.根据mid锁定的元素和查找的元素比较，确定新的查找范围left和right

下面将用图示和代码来讲解上面的三个步骤：

1.假定给定的数组中元素个数为奇数个

2.假定给定的数组为偶数个

3.假定给定的数不在此数列中

根据以上这三种情况，代码可以写成如下形式：

#include <stdio.h>
int main()
{
    int arr[] = { 1,2,3,4,5,6,7,8,9,10,11,12,13 };
    int left = 0, right = sizeof(arr) / sizeof(arr[0]) - 1;
    int x = 0,flag = 0;

    scanf("%d", &x);//要找的数

    while (left <= right)//若要找的数在此数组中，此条件会一直成立；
                         //若要找的数不在此数组中，最终left会大于right,从循环中跳出
    {
        int mid = (left + right) / 2;
        if (x == arr[mid])
        {
            printf("%d
", mid);
            flag = 1;
            break;
        }
        else if (x > arr[mid])
        {
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }
    if (flag == 0)//只有当要找的数在数组中找不到时flag == 0
    {
        printf("找不到
");
    }
    return 0;
}

总结：从上面的例子可以看出，二分法求解是一种很高效的方法，因为一次就可以排除一半的可能性。但也要注意，二分法只适用于有序数列

二、分支语句中应注意的小点

1.悬空else语句

#include <stdio.h>
int main()
{
	int a = 0;
	int b = 2;
	if (a == 1)
		if (b == 2)
			printf("hehe
");
		else
			printf("haha
");
	return 0;
}

在上面的代码中，有人可能就会对else语句与哪个if语句配对产生误解。

其实：else是和它离的最近的if匹配的。但如果是像上面那样写就容易引起歧义。可以写成下面的形式：

#include <stdio.h>
int main()
{
	int a = 0;
	int b = 2;
	if (a == 1)
	{
		if (b == 2)
		{
			printf("hehe
");
		}
	}
	else
	{
		printf("haha
");
	}
	return 0;
}

适当的使用{}可以使代码的逻辑更加清楚。

2.switch语句中的break

switch允许嵌套使用

#include <stdio.h>
int main()
{
	int n = 1;
	int m = 2;
	switch (n)
	{
	case 1:
		m++;//m == 3
	case 2:
		n++;//n == 2
	case 3:
		switch (n)
		{//switch允许嵌套使用
		case 1:
			n++;
		case 2:
			m++;//m == 4
			n++;//n == 3
			break;
		}
	case 4:
		m++;//m == 5, n == 3
		break;
	default:
		break;
	}
	printf("m = %d, n = %d
", m, n);
	return 0;
}

上面代码中，有的case语句后没有加上break,这就会导致执行完一条没有加break的case语句后还会执行其下面的一条case语句，可能就会导致跟我们想要的判断输出结果不同。因为switch更多时候执行的是条件判断的功能，所以最好