折半查找算法

⑴ 设计折半查找的算法

/*
这里给出一个int数组的查找
b_sch()函数的参数中第一个为要查找的数组
这个数组必须是有序，我给的这个程序要求从小到大排序
这个数组必须不存在重复元素，否则会影响结果
注意l（L）和1（一）的区别，计算机给出的这两个字符很相似
*/
intb_sch(int*s,intl,intr,intkey)//s是要查找的数组，l是数组的第一个元素下标
//r是数组最后一个元素下标，key是要查找的元素
{
while(l<=r)//当l<=r时，也就是说在应该查找的范围内
{
intmid=(l+r)/2;//二分，也就是折半
if(s[mid]==key)//如果mid和要查找的元素相等返回这个下标
returnmid;
elseif(key>s[mid])//如果要查找的元素在mid的右边，也就是说
//比s[mid]大，那么说明要查找的元素应该在，mid到r这个区间内
//那么就把范围缩小在mid+1到r区间内，所以，最前面的元素下标
//就要改成mid+1，也就是l=mid+1
l=mid+1;
else
r=mid-1;//和上面同理，这个就是右边元素下标变化
}
return-1;//查找失败，返回-1
}

⑵ c语言折半查找法

折半查找法是算法一种，可以被任何计算机语言使用。用C语言自然也可以实现。

1、定义：

在计算机科学中，折半搜索（英语：half-interval search），也称二分搜索（英语：binary search）、对数搜索（英语：logarithmic search），是一种在有序数组中查找某一特定元素的搜索算法。

搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

2、查找规则：

折半查找法是效率较高的一种查找方法。假设有已经按照从小到大的顺序排列好的五个整数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，说明没有此数，打印找不到信息，程序结束。

3、C语言参考代码：

intbin_search(intA[],intn,intkey){
//在长度为n的数组A中折半查找值为key的元素，并返回下标值。如果不存在则返回-1.
intlow,high,mid;
low=0;
high=n-1;//初始low和high为数组的两端。
while(low<=high)
{
mid=(low+high)/2;//查找中心点。
if(A[mid]==key)returnmid;//已找到，返回下标值。
if(A[mid]<key){//中点位置比key值小，以mid+1为新的下限值。
low=mid+1;
}
if(A[mid]>key){//中点位置比key值大，以mid-1为新的上限值。
high=mid-1;
}
}
return-1;//未找到，返回-1.
}

⑶ C语言中的折半查找法是什么

折半查找的前提是已经对数据做好了排序，然后再折半查找
例如排序后的数据是1 5 12 35 64 78 89 123 456
你要查找12，首先用12跟上面排好顺序的9个数中间那个比较（64），12<64，因此你查找的数据在前半部分，即
1 5 12 35 64，再用12跟前半部分中间那个数比较（12），这样找了2次就找到了
折半查找的目的是提高查找的效率 折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。
【基本思想】
将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如果x<a[n/2]，则我们只要在数组a的左半部继续搜索x（这里假设数组元素呈升序排列）。如果x>a[n/2]，则我们只要在数组a的右半部继续搜索x。
二分搜索法的应用极其广泛，而且它的思想易于理解。第一个二分搜索算法早在1946 年就出现了，但是第一个完全正确的二分搜索算法直到1962年才出现。Bentley在他的着作《Writing Correct Programs》中写道，90%的计算机专家不能在2小时内写出完全正确的二分搜索算法。问题的关键在于准确地制定各次查找范围的边界以及终止条件的确定，正确地归纳奇偶数的各种情况，其实整理后可以发现它的具体算法是很直观的。 刚开始的时候数组时排好顺序的：从小到大，或者从大到小。然后将这个数组折中，用中间的这个数和要查找的数比较大小，（例如：如果我从小到大，我将数组这种后，用中间的数和要查找的数比较，如果小

⑷ 用递归法写一个折半查找的算法

// 二分查找前提数组元素已按升序排序
int binsearch(int value, int a[], int nArrayLen)
{
int nMid = nArrayLen / 2;

if (value == a[nMid])

return nMid; // 找到下标

if (nMid == 0)

return -1; // 找不到

if (value < a[nMid])
return binsearch(value, a, nMid);

else

return binsearch(value, a + nMid, nArrayLen - nMid);

}

⑸ 折半查找法的概念是什么

对一个已经排好序的数组，先看中间的元素是不是要求元素。如果是就找到了，不是看比要找的元素大还是小，大的话，上前一部分用同样的方法再找，小的话去后一部分用同样的方法再找

⑹ 折半查找算法设计

请查看数据结构朱站立版第，第5、6、10、11章节，先排序，再查找

⑺ 折半查找法的基本算法实现

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;
} #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(请输入您要查找的数: );
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位 ,mid); break; }
}
if(n==a[max]) printf(输入的数在数列的第%d位 ,max);
else if(n==a[min]) printf(输入的数在数列的第%d位 ,min);
else if(n!=a[mid]) printf(输入的数不在数列中);
return 0;
} #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个元素的值。 ,mid+1);
m=0;
break;
}
else if(n>a[mid])
top=mid+1;
else if(n<a[mid])
bot=mid-1;
}
if(m)
printf(无此数。 );
system(PAUSE);
return 0;
}

⑻ 数据结构折半查找算法的方法

041424344#include <stdio.h> int Dichotomy(int a[],int _value,int n){ // 二分法(也称折半查找法) int index=0; // 当前数组的首元素下标 int current=n-1; // 数组当前的大小 int k; // 当前数组中间的数的下标 while (index<current) { // 开始二分法查找 k=(index+current)/2; // 除以2代表得到当前数组中间的数的下标 if(a[k]==_value) return k; // 返回要查找的值_value所在的下标 // 否则比较要查找的值_value是在折半后的前半部分还是后半部分 if(a[k]<_value){ // 说明要查找的值在折半后的后半部分 index=k+1; // 令index指向后半部分数组的首元素 } else{ // 说明要查找的值在折半后的前半部分 current=k-1; // 令current等于前半部分数组的长度 } } return -1; // 返回-1代表没有查找到该值(_value)}void main(){ int arr[5]={2,12,45,87,95};// 前提是一组数组必须是有序数对(即按小到大或大到小) if(Dichotomy(arr,87,5)!=-1) printf("87在数组中对应的下标是:%d\n",Dichotomy(arr,87,5)); else printf("没有找到指定的值\n");}// 用一句话概括二分法(折半查找法)的思想就是:在一组有序对数组中反复折半后得到中间数组的下标,然后再进行是否与要查找的值相等,若相等则返回当前要查找的值的下标。 那么，上面的代码的注释与下面一一对应，它在执行的结果会产生两种情况，第一种,不存在。第二种，存在。先来说说第一种情况 不存在： 1.如果给定要查找的值_value大于数组中最大的数,则index不断增大从而促使while循环终止 2.如果给定要查找的值_value小于数组中最小的数,则current不断减少从而促使while循环终止(你自己可以动手在纸上画一个数组,然后思路跟着代码走就会知道或设单步调试亦可) 第二种情况 存在： 1.要查找的数_value正好是在数组中间.那么就执行了一次循环,当然这也是最理想的效果. 否则反复执行2和3:2.如果要查找的数_value不存在中间,则判断它是否大于中间的数还是小于中间的数,如果小于中间的数则说明_value应该在数组中间的前半部分,那么current=k-1(即令current等于前半部分的长度),然后仍然采取折半的方法,反复此操作直至找到该数的下标为止. 3.如果要查找的数_value不存在中间,则判断它是否大于中间的数还是小于中间的数,如果大于中间的数则说明_value应该在数组中间的后半部分,那么index=k+1(即令index指向后半部分的第一个下标),然后仍然采取折半的方法,反复此操作直至找到该数的下标为止.

⑼ 折半查找的算法怎么写 C语言

#include<stdio.h>
void main()
{
int in[15],ins,i,k=14,j=0;
printf("请按照从小到大的顺序输入15个数\n");
for(i=0;i<15;i++) scanf("%d",&in[i]);
printf("请输入要查找的数:");
scanf("%d",&ins);
i=(j+k)/2;
while(j<=k)
{
if(in[i]>ins)
k=i-1;
else
if(in[i]<ins)
j=i+1;
else break;
i=(j+k)/2;
}
printf("你查找的是其中的第%d个数。",i+1);/*i是他的存储的顺序数，i+1才是他在输入数组中的位置数*/
}

⑽ 什么是折半查找法

#include <stdio.h>
#define N 51
void main(void)
{
int a[N];
int i,n,num;
int top,bottom,mid;
int flag=1; //如果在表列中找到数字，则值为1，否则为0
int loc=-1;//要查找的数在表列中的位置，如果loca=-1表示表列中没有这个数;如果有这个数,则它的值为所在的位置
printf("你想在多少个数中进行折半查找，请输入（1--50）：");
scanf("%d",&n);
while(n<1 || n>50)
{
printf("你输入的数不正确，请重新输入。\n");
printf("你想在多少个数中进行折半查找，请输入（1--50）：");
scanf("%d",&n);
}
printf("请你输入一个整数 a[1](需保证递增有序):");
scanf("%d",&a[1]);
i=2;
while(i<=n) //输入从小到大的表列
{
printf("请你输入一个整数 a[%d](需保证递增有序):",i);
scanf("%d",&a[i]);
if(a[i] > a[i-1])
i++;
else
printf("你输入的数不满足要求，请重新输入。\n");
}
//输出表列
printf("\n输出表列\n");
for(i=1; i<=n; i++)
{
printf("%6d",a[i]);
}
printf("\n");
printf("请你输入要查找的数：");
scanf("%d",&num);
flag=1; //假设输入的数在表列中
top=n;
bottom=1;
mid=(top+bottom)/2;
while(flag)
{

//printf("top=%d, bottom=%d, mid=%d, a[%d]=%d\n",top,bottom,mid,mid,a[mid]);
if( (num>a[top]) || (num<a[bottom]) ) //输入的数 num>a[top] 或者
num<a[bottom]，肯定num不在这个表列中
{
loc=-1;
flag=0;
}
else if(a[mid]==num) //如果num 等于找到的数
{
loc=mid;
printf("找到数 %6d 的位置%2d\n",num,loc);
break;
}
else if(a[mid]>num) //若 a[mid]>num，则num 一定在 a[bottom]和a[mid-1]范围之内
{
top=mid-1;
mid=(top+bottom)/2;
}
else if(a[mid]<num) //若 a[mid]<num，则num 一定在 a[mid+1]和a[top]范围之内
{
bottom=mid+1;
mid=(top+bottom)/2;
}
}
if(loc==-1)
{
printf("%d 这个数在表列中没有找到。\n",num);
}
printf("折半查找结束,按任意键退出：\n");

}