求查找算法(折半查找法,顺序查找法,分别在一个程序里)“动画演示”程序...
发布网友
发布时间：2022-04-29 10:50
共2个回答
懂视网
时间：2022-04-24 06:29
本文实例讲述了JS数组搜索之折半搜索实现方法。分享给大家供大家参考，具体如下：
一. 方法原理：
当从一个给定的序列数组arr中, 查找某个特定值value时, 折半搜索法是这样做的:
1. 确定搜索范围的起始点: 起点startIndex = 0, 终点endIndex = arr.length - 1;
2. 根据起始点来确定一个中间点middle = Math.floor((终点 - 起点) / 2);
3. 在startIndex < endIndex的前提下, 比较arr[middle]与value的大小:
(1) arr[middle] < value
调整搜索范围为数组的后半部分, 即startIndex = middle + 1, endIndex = arr.length -1;
(2) arr[middle] > value
调整搜索范围为数组的前半部分, 即startIndex = 0, endIndex = middle - 1;
接着, 重新计算middle, 再比较arr[middle]与value, 直到两者相等或者startIndex >= endIndex.
二. 代码：
三. 优缺点：
(1) 优点:
每查找一次, 被查找的数组项数量会减少一半, 因此其在性能上要优于线性搜索法(在数组项较多时, 尤其明显);
(2) 缺点:
只适用于序列数组, 在对普通数组使用该方法之前, 需要对数组进行排序
热心网友
时间：2022-04-24 03:37
折半搜索（英语：half-interval search），也称二分搜索（英语：binary search）、对数搜索（英语：logarithmic search），是一种在有序数组中查找某一特定元素的搜索算法。
搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
折半查找法是效率较高的一种查找方法。假设有已经按照从小到大的顺序排列好的五个整数a0~a4，要查找的数是X，其基本思想是： 设查找数据的范围下限为l=0，上限为h=4，求中点m=（l+h）/2，用X与中点元素am比较，若X等于am，即找到，停止查找；否则，若X大于am，替换下限l=m+1，到下半段继续查找；若X小于am，换上限h=m-1，到上半段继续查找；如此重复前面的过程直到找到或者l>h为止。如果l>h，说明没有此数，打印找不到信息，程序结束。
函数实现如下：
bin_search(int A[],int n,int key){int low,high,mid;
low = 0;
high = n-1;
while(low<=high)
{
mid =(low + high)/2;
if(A[mid]==key)return mid;
if(A[mid]<key){
low =mid + 1;
}
if(A[mid]>key){
high= mid - 1;
}
}
return -1;
}
C语言实现代码
#include <stdio.h>int main()
{
int a[11]={0,1,2,3,4,5,6,7,8,9,10},min=0,max=10,mid,n; //max为数列长度，a[0]作为第一个数组元素
printf("请输入您要查找的数:\n");
scanf("%d",&n);
while(min+1!=max)
{
mid=(min+max)/2;
if (n>a[mid]) min=mid;
else if (n<a[mid]) max=mid;
else
{
printf("输入的数在数列的第%d位\n",mid);
exit(0);
}
}
if(n==a[max])
{
max+=1;
printf("\n输入的数在数列的第%d位\n",max);
}
else if(n==a[min])
{
min+=1;
printf("\n输入的数在数列的第%d位\n",min);
}
else if(n!=a[mid])
printf("\n输入的数不在数列中");
}
Dev-c++实现
#include <stdio.h>
#include <stdlib.h>
void main()
{
int a[15]={1,2,3,4,5,6,7,8,9,10,11,12,13,15};
int n,m,top,bot,mid;
top=m=1; //此处修改top=0;m=1;
bot=14;
printf("please input a number:");
scanf("%d",&n);
while(top<=bot)
{
mid=(top+bot)/2;
if(n==a[mid])
{
printf("这是第%d个元素的值。\n",mid+1);
m=0;
break;
}
else if(n>a[mid])
top=mid+1;
else if(n<a[mid])
bot=mid-1;
}
if(m)
printf("无此数。\n");
system("PAUSE");
return 0;
}
顺序查找是按照序列原有顺序对数组进行遍历比较查询的基本查找算法。
对于任意一个序列以及一个给定的元素，将给定元素与序列中元素依次比较，直到找出与给定关键字相同的元素，或者将序列中的元素与其都比较完为止。
函数实现如下：
int sq_search(keytype keyp[],int n,keytype key){
int i;
for(i=0; i<n; i++)
if(key[i] == key)
return i;//查找成功
return -1;//查找失败
}
上面只是算法实现函数，对于动画部分，自己用moveto，lineto描点划线的方式实现吧。
追问敢谢您的指点，我大一刚学完c，moveto,lineto的用法老师都没讲，所以我还不会应用，您方便给我这个顺序查找法动画演示的源代码吗?我想自己摸索着写出折半查找法追答moveto（50,50）是将画笔移动到参数指定的坐标（50,50）
lineto（150,50）是从画笔的当前位置绘制一条直线到参数给的坐标（150,50）
所以这两句的结果就是画了一条直线，从50,50开始到150,50结束
这两个函数不难的
说白了moveto和lineto就是用来画曲线的，不知道你要的动画是哪种动画
