江苏省海安高级中学高中信息技术选修 算法与程序设计 二分法查找 维数组的应用(共9张PPT)

一维数组、二维数组 一维数组的查找 A.顺序查找　　 B.二分查找 一维数组的查找（顺序查找） （一本通P86练习1 查找指定数字的个数） cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; cin>>m; for(int i=1;i<=n;i++){ if(a[i]==m)； t++; } cout<<t<<endl; cin>>n; for(int i=1;i<=n;i++){ cin>>t; 　a[t]++; } cin>>m; cout<<a[m]<<endl; 顺序查找，逐个比对。 先预处理，然后直接输出。 利用一维数组进行预处理优化，提高查找的效率。 a[0] int a[1001]={0}; a[1000] cin>>t; a[t]++; 数据输入：8 5 5 1 a[1] a[5] a[8] cout<<a[5]; 0 0 0 0 0 0 0 0 0 0 0 0 0 …… 0 0 0 0 1 0 0 0 2 0 0 1 0 0 0 0 …… 0 0 0 一维数组的查找（二分查找） 二分查找又称折半查找，是对有序的数据表进行的高效查找方法。 算法描述： (1)设置三个指针low，high,mid表示查找区间的左端点、右端点和中间位置； (2)当low<=high时，二分查找； a.如果目标值大于mid单元值,则low=mid+1,继续二分; b.如果目标值小于mid单元值,则high=mid-1,继续二分 ; c.如果目标值等于mid单元值，返回查找结果并退出查找; (3)返回没有查到。 例：查找值为14的记录的过程： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 7 14 18 21 23 29 31 35 38 42 46 49 52 14<31 14<18 14>7 14=14 low=1 high=13 mid=7 high=6 mid=3 high=2 mid=1 low=2 mid=2 例：查找值为22的记录的过程： 0