Question

C++折半查找的基本思想和步骤

急求C++折半查找的基本思想和步骤<详细的>

Answer 1

折半查找法是效率较高的一种查找方法。

基本思想是：设查找数据的范围下限为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，说明没有此数，打印找不到信息，程序结束。

步骤：

1、首先确定整个查找区间的中间位置 mid=（ left + right） /2 。

2、用待查关键字值与中间位置的关键字值进行比较；若相等，则查找成功，若大于，则在后（右）半个区域继续进行折半查找，若小于，则在前（左）半个区域继续进行折半查找。

3、对确定的缩小区域再按折半公式，重复上述步骤。最后得到结果：要么查找成功，要么查找失败。折半查找的存储结构采用一维数组存放。

扩展资料

折半查找法的优点：比较次数少，查找速度快，平均性能好；

缺点：是要求待查表为有序表，且插入删除困难。

因此，折半查找方法适用于不经常变动而查找频繁的有序列表。

参考资料：百度百科-折半查找法

Answer 2

二分法查找算法又叫折半查找。其思想是将已排好序的数列依次存入数组，设查找数值为X，用指针bot指向数列最左端位置（最小值），指针top指向数列最右端位置（最大值），取bot和top的中间值mid指向数列中间。

具体步骤解释如下：当top>bot时，比较查找X与a[mid]，有3种可能。

1. 若X = a[mid]，则表示找到，退出比较查找。

2. 若X < a[mid]，则选择前半段继续比较查找，bot不变，top变成mid-1。

3. 若X > a[mid]，则选择后半段继续比较查找，bot变成mid+1，top不变

结束过程有两种：一种是找到了X = a[mid]；另一种是没找到，即top < bot。

拓展资料：

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

参考资料：百度百科 二分查找法的不同类型代码写法

Answer 3

算法思想：

折半查找（Binary Search）的查找过程是：先确定等查记录所在范围（区间），然后逐步缩小范围直到找到或找不到该记录为止。

步骤如下：

比较x和a的中间元素a[mid]，

若x=a[mid]，则x在L中的位置就是mid；

如果x<a[mid]，则x在a[mid]的前面；

如果x>a[mid]，则x在a[mid]的后面。

无论在哪部分查找x，其方法都和在a中查找x一样，只不过是查找的规模缩小了。这就说明此问题满足分治法的第二个和第三个适用条件。

拓展资料

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

Answer 4

#include<iostream>using namespace std;#define N 10 int half(int s[],int a,int b,int key) { int mid;if(a==b) if(key==s[a]) return (a); else return (-1); else { mid=(a+b)/2; if(key<s[mid]) return(half(s,a,mid,key)); if(key>s[mid]) return(half(s,mid+1,b,key)); if(key==s[mid]) return (mid); } } int main(){int i=0,s[N],key,t;cout<<"请输入"<<N<<"数字："<<endl;for(i=0;i<N;i++) cin>>s[i];cout<<"请输入你要查询的数"<<endl;cin>>key;t=half(s,0,N,key);if(t==-1) cout<<"没有这个数"<<endl;else cout<<t+1<<endl;return 0;}
答案补充
在对数列查找之前,可能已经知道了数列的许多相关信息。比如说,知道了有序数列的大体分布等。如果知道了有序数列中每相邻两个元素之差的最大值的一个上界,这时可以在每次循环做折半之前先进行一次筛选工作,把尽可能多的不必要的元素过滤掉,这样可以极大地提高查找速度。其最坏情况下查找一个元素的最大比较次数将介于1和[ log2 n ] + 1 ( n为元素的个数)之间。另外,在实际的很多应用中可通过在建立有序数列的过程中同时得到M。比如说在建立数组的过程中可根据插入新元素的情况不断地更新M,从而在每次查找的过程中极大地提高效率

Answer 5