/***********************************************************************
目的：在有序数组中查找数字
分析：遍历数组即可
平台：Visual studio 2017 && windows
*************************************************************************/
#include<stdio.h> int main() { int arr[] = {1,2,3,4,5,6,7,8,9,10}; int k = 7;//要查找的数字 int i = 0; int sz = sizeof(arr)/sizeof(arr[0]);//数组元素个数 for(i=0; i<sz; i++)//遍历数组 { if(arr[i] == k) printf("要查找的数字的下标是%d\n", i); } return 0; }
/***********************************************************************
目的：遍历数组的方法效率低，使用二分查找/折半查找法优化代码
分析：🍳算法思想： 二分查找是针对的是一个有序的数据集合，每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为0
时间复杂度log2^n 。假如要计算2^32个数据只要32次
平台：Visual studio 2017 && windows
*************************************************************************/
#include<stdio.h> int main() { int arr[] = { 1,2,3,4,5,6,7,8,9,10 }; int k = 7;//要查找的数字 int sz = sizeof(arr)/sizeof(arr[0]); int left = 0;//左下标 int right = sz-1;//右下标 = 元素个数-1 while(left <= right) { int mid = (left+right)/2;//确定中间下标 if(arr[mid] < k) { left = mid + 1;//因为arr[mid]<k，所以排除arr[mid] } else if(arr[mid]>k) { right = mid - 1; } else { printf("找到了，下标是%d\n", mid); break; } } if(left > right) { printf("找不到\n"); } return 0; }
