以前,我们查找数组元素都是利用for循环进行下标索引去查找我们想要的元素,但是今天呢,我想对比循环和二分法两种不同方式的差距,让我们在以后学习或者工作中更加便捷,快速,高效的去做一些项目
让我们一起开始今天的学习之旅吧
循环方式查找数组元素
给定一个数组arr让我们通过代码寻找自己想要查找的元素
for 循环方式
#include<stdio.h> int main() { int arr[] = { 1,2,3,4,5,6,7,8,9,10 }; // 0,1,2,3,4,5,6,7,8,9 int i = 0; scanf("%d", &i); int j = 0; int sz = sizeof(arr) / sizeof(arr[0]); int find = 0;//假设找不到 for (j = 0; j < sz; j++) { if (i == arr[j]) { printf("找到了,下标是%d\n",j); find = 1; break; } } if (find == 0) { printf("找不到了\n"); } return 0; }
个人注意:在if判断语句中判断两个数是否相等要用==,否则会直接退出程序
二分法查找数组元素
二分法:顾名思义,就是一分为二,这个"一"就好比如两瓶高度不同的水的差值,然后将高的那一部分倒入高度为它们原来差值一半的水给另一杯,使得两杯水达到相同高度.
二分查找使用条件:元素有序排列
二分法方式
#include <stdio.h> int main() { int arr[] = { 1,2,3,4,5,6,7,8,9,10 }; // 0,1,2,3,4,5,6,7,8,9 int i = 0; scanf("%d", &i); 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 (i < arr[mid]) { right = mid - 1; } else if (i > arr[mid]) { left = mid + 1; } else { printf("找到了,下标是%d\n", mid); find = 1; break; } } if (find == 0) { printf("找不到了\n"); } return 0; }
总结
1.二分法相对于for循环可以节省一半的时间
2.二分法做这种题的思路:先设需要的变量,然后根据变量关系写出相应的变化向目标范围不断前进,然后再考虑是否需要做多次这种行为,最后再考虑其它情况.
