遍历数组法
在有序数组中查找某个特定的值,那我们就直接遍历整个数组就行了,这是最简单的一种方法
#include<stdio.h> int main() { int arr[10] = { 1,2,3,4,5,6,7,8,9,10 }; int k = 7; int i = 0; for (i = 0; i < 10; i++) { if (7 == arr[i]) printf("找到了是下标为%d\n", i); } return 0; }
这样的方法确实简单,但是效率比较低。接下来我们就进入重点我们介绍二分查找法(也叫折半查找法)
二分查找法
为什么上面的那个不好呢?打个比方。假如你买了一件羽绒服,让我来猜猜你花了多少钱,我难道是从1开始猜吗?我可能会说300?350? 400?
这样才更贴近生活
int main() { int arr[10] = { 1,2,3,4,5,6,7,8,9,10 }; int num = sizeof(arr) / sizeof(arr[0]); int left = 0; int right = num - 1; int mid = left + right / 2; return 0; }
利用sizeof的这个语句,我们能够知道数组一共有多少元素,left 是 int 类型因为我们等下要用它从当数组的下标,right 的值为num-1 也就是10 -1 =9 ,9就是最后一个元素的下标,mid 就是用两数的平均数得出。
接下来我们再接着讲解。
left 变成了mid+1也就是 arr[mid+1],但是我们要将arr[mid ]与7比较才能知道要排除那些值,那怎么办呢?
我们就应该再换一个arr[mid]来与7比较,这里也有循环的意思了。
再变化
最后一步分析
最后咱们再把arr[mid]与7比较一下,发现两者相等就行了。
总代码过程
我们看完这个过程一个就知道这是个循环,你也可以自己试一试,不会再看下面的过程,当然只供参考,每个人有其独特的想法
#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> int main() { int arr[] = { 1,2,3,4,5,6,7,8,9,10 }; int k = 7; int num = sizeof(arr) / sizeof(arr[0]); int left = 0;//左下标 int right = num - 1;//右下标 while (left <= right) { 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; } } if (left > right) { printf("找不到了\n"); } return 0; }
这个代码要注意几个点, 第一点:就是要学会计算数组元素(利用sizeof),第二点:要注意每次与K比大小后要把mid的值改变,最后:要注意while()里的条件,这个写<=而不是< 是因为当left right mid都在一个地方时,还是需要进行一次比较,才算真正找到,不然当left与right相等时,是不会再计算mid的就是说,else的语句是不会进去的,也就不会告诉你 找到没有。
你也可以试试把K值设为3 自己再分析一遍,巩固一下。
这篇文章就到这里了,作者能力有限,如有错误请大胆指出。
最后都看到这里请点个赞把,这对我真的很重要