C语言二分查找图文详解
折半查找法也叫做二分查找,顾名思义就是把数据分成两半,再判断所查找的key在哪一半中,再重复上述步骤知道找到目标key,这篇文章主要给大家介绍了关于C语言二分查找的相关资料,需要的朋友可以参考下
一、二分查找算法
所谓二分查找，就是要在一组有序的数列中，查找给定的数是否在此数列中。
最主要的步骤有三个：
1.确定被查找的范围的左右下标left、right
2.根据left和right，确定中间元素的下标mid
3.根据mid锁定的元素和查找的元素比较，确定新的查找范围left和right
下面将用图示和代码来讲解上面的三个步骤：
1.假定给定的数组中元素个数为奇数个
2.假定给定的数组为偶数个
3.假定给定的数不在此数列中
根据以上这三种情况，代码可以写成如下形式：
#includeint 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\n", mid); flag = 1; break; } else if (x > arr[mid]) { left = mid + 1; } else { right = mid - 1; } } if (flag == 0)//只有当要找的数在数组中找不到时flag == 0 { printf("找不到\n"); } return 0; }
总结：从上面的例子可以看出，二分法求解是一种很高效的方法，因为一次就可以排除一半的可能性。但也要注意，二分法只适用于有序数列
二、分支语句中应注意的小点
1.悬空else语句
#includeint main() { int a = 0; int b = 2; if (a == 1) if (b == 2) printf("hehe\n"); else printf("haha\n"); return 0; }
在上面的代码中，有人可能就会对else语句与哪个if语句配对产生误解。
其实：else是和它离的最近的if匹配的。但如果是像上面那样写就容易引起歧义。可以写成下面的形式：
#includeint main() { int a = 0; int b = 2; if (a == 1) { if (b == 2) { printf("hehe\n"); } } else { printf("haha\n"); } return 0; }
适当的使用{}可以使代码的逻辑更加清楚。
2.switch语句中的break
switch允许嵌套使用
#includeint 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\n", m, n); return 0; }
上面代码中，有的case语句后没有加上break,这就会导致执行完一条没有加break的case语句后还会执行其下面的一条case语句，可能就会导致跟我们想要的判断输出结果不同。因为switch更多时候执行的是条件判断的功能，所以最好
在每一条有效的case语句后面都加上break。同时也要注意，在每个 switch 语句中都放一条default子句是个好习惯，甚至可以在后边再加一个 break 。
总结
到此这篇关于C语言二分查找的文章就介绍到这了,更多相关C语言二分查找内容请搜索0133技术站以前的文章或继续浏览下面的相关文章希望大家以后多多支持0133技术站！
标签：