分块查找算法

㈠ 分块查找算法中如何对数据分块

可以实现确定待查找数据的上限和下限，
然后对该区间等分N块，
那么这N块就可以作为分块查找的块，
然后将原数组中的元素按区间插入进去，
当然，这样划分不能保证每个块中的元素个数相等，
但是，分块查找算法并不严格要求每块中的元素的个数相等。

㈡ 求分块查找算法 最好有代码和详细注释

注意：采用“二分查找”时，初始的数组或其他线性表中的每个元素都必须是按一定的顺序排列的（从大到小，或从小到大），
该算法的基本思想：对一个有序数据序列，总是先把查找目标与该序列的中间的元素进行比较，我们假设该序列是由从小到大排列的，if(key > data[mid]),则key一定在data[mid]的又边，于是，把mid到序列data[end]分成一块，此时mid = (mid + end) / 2,依次类推

参考程序：

#include<stdio.h>
#define MAXSIZE 26 //定义索引表的最长长度
typedef char TYPE;

int blksearch(TYPE R[],TYPE K);
void main()
{
int num, i;
TYPE R[N + 1];
TYPE K;

for(i = 0;i<N;i++)
R[i]='a'+i;
printf("\nplease input the key number:\n");
K=getchar();
num=blksearch(R,K);

if(num!=-1)
printf("第%d个是关键字\n",num+1);
else
printf("查找失败！\n");
}

int blksearch(TYPE R[],TYPE K) //分块查找
{
int low1,mid,high1;
low1=0;
high1=N - 1; //二分查找区间上下界初值
while(low1<=high1)
{
mid=(low1+high1)/2;

if(K < R[mid])
high1=mid-1;
else
if(K > R[mid])
low1=mid+1;
else
return mid; //如果找到key，立即返回key的位置

}
return -1;// 只要上面的return语句没执行，则原数组中无key，返回-1

}

㈢ 分块检索中，若索引表和各块内均用顺序查找，则有900个元素线性表，若分成25块，求其平均查找长度

长度为n(900)的表分成均等的b（25）个子表，则每个子表的长度为s，b=n/s（900/25=36）。

顺序查找时成功的平均查找长度为：

（b+s)/2+1=(25+36)/2+1=44

例如：

每块最佳长度为：根号625= 25，即每块25个结点，一共分为25块，此时平均查找长度=2((25+1)/2)= 26

(3)分块查找算法扩展阅读：

分块查找的速度虽然不如折半查找算法，但比顺序查找算法快得多，同时又不需要对全部节点进行排序。当节点很多且块数很大时，对索引表可以采用折半查找，这样能够进一步提高查找的速度。

分块查找由于只要求索引表是有序的，对块内节点没有排序要求，因此特别适合于节点动态变化的情况。当增加或减少节以及节点的关键码改变时，只需将该节点调整到所在的块即可。在空间复杂性上，分块查找的主要代价是增加了一个辅助数组。

㈣ 如何用C++描述分块查找的算法

template<class Type>

int BinarySearch(Type a[],const Type& x,int n)

{

int left=0;

int right=n-1;

while(left<=right){

int middle=(left+right)/2;

if (x==a[middle]) return middle;

if (x>a[middle]) left=middle+1;

else right=middle-1;

}

return -1;

}

模板函数BinarySearch在a[0]<=a[1]<=...<=a[n-1]共n个升序排列的元素中搜索x,找到x时返回其在数组中的位置，否则返回-1。容易看出，每执行一次while循环，待搜索数组的大小减少一半,因此整个算法在最坏情况下的时间复杂度为O(log n)。在数据量很大的时候，它的线性查找在时间复杂度上的优劣一目了然。
选择排序
基本思想是：每次选出第i小的记录，放在第i个位置（i的起点是0，按此说法，第0小的记录实际上就是最小的，有点别扭，不管这么多了）。当i＝N－1时就排完了。

直接选择排序
直选排序简单的再现了选择排序的基本思想，第一次寻找最小元素的代价是O(n)，如果不做某种特殊处理，每次都使用最简单的寻找方法，自然的整个排序的时间复杂度就是O(n2)了。

冒泡法
为了在a[1]中得到最大值，我们将a[1]与它后面的元素a[2]，a[3]，...，a[10]进行比较。首先比较a[1]与a[2]，如果a[1]<a[2]，则将a[1]与a[2]交换，否则不交换。这样在a[1]中得到的是a[1]与a[2]中的大数。然后将a[1]与a[3]比较，如果a[1]<a[3]，则将a[1]与a[3]交换，否则不交换。这样在a[1]中得到的是a[1]，a[2]，a[3]中的最大值，...。如此继续，最后a[1]与a[10]比较，如果a[1]<a[10]，则将a[1]与a[10]交换，否则不交换。这样在a[1]中得到的数就是数组a的最大值（一共进行了9次比较）。

为了在a[2]中得到次大值，应将a[2]与它后面的元素a[3]，a[4]，...，a[10]进行比较。这样经过8次比较，在a[2]是将得到次大值。

如此继续，直到最后a[9]与a[10]比较，将大数放于a[9]，小数放于a[10]，全部排序到此结束。
从上面可以看出，对于10个数，需进行9趟比较，每一趟的比较次数是不一样的。第一趟需比较9次，第二趟比较8次，...，最后一趟比较1次。

以上数组元素的排序，用二重循环实现，外循环变量设为i，内循环变量设为j。外循环重复9次，内循环依次重复9，8，...，1次。每次进行比较的两个元素，第一个元素与外循环i有关的，用a[i]标识，第二个元素是与内循环j有关的，用a[j]标识，i的值依次为1,2,...,9，对于每一个i, j的值依次为i+1,i+2,...。

㈤ 什么是分块查找法

分块查找又索引查找，它主要用于“分块有序”表的查找。所谓“分块有序”是指将线性表L（一维数组）分成m个子表（要求每个子表的长度相等），且第i+1个子表中的每一个项目均大于第i个子表中的所有项目。“分块有序”表应该包括线性表L本身和分块的索引表A。因此，分块查找的关键在于建立索引表A。
（1）建立索引表A（二维数组）
索引表包括两部分：关键字项（子表中的最大值）和指针项（子表的第一项在线性表L中位置）
索引表按关键字有序的。
例如：线性表L（有序）为：1 2 3 4 5 6 7 8 9 10 11 12
分成m=3个子表：{1 2 3 4} {5 6 7 8} {9 10 11 12}
索引表A：二维数组：第一列为每个子表的最大值 ，第二列为每个子表的起始地址
即： 4 0
8 4
12 8
（2）利用索引表A，确定待查项X所在的子表（块）。
（3）在所确定的子表中可以用“折半查找”法搜索待查项X；若找到则输出X；否则输出未找到信息。
我不懂，谁能给我解释一下，最好有例题分析

㈥ 分块查找 怎么分块

你好，分块查找的效率是介于顺序查找和折半查找之间的。但是折半查找要求整个线性表都是有序表，而分块查找只要求每块都有序，并不是整个线性表都有序，当一个线性表存在明显的可以分为一块一块时，分块查找就会快于折半查找。选用什么查找方法不能一概而论，要依具体情况来选择。如果还有什么疑问，欢迎继续提问。

㈦ 什么是查找法

算法思想：

将数列按有序化(递增或递减)排列，查找过程中采用跳跃式方式查找，即先以有序数列的中点位置为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。通过一次比较，将查找区间缩小一半。

折半查找是一种高效的查找方法。它可以明显减少比较次数，提高查找效率。但是，折半查找的先决条件是查找表中的数据元素必须有序。

算法步骤描述：

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

step2 用待查关键字值与中间位置的关键字值进行比较；

若相等，则查找成功

若大于，则在后（右）半个区域继续进行折半查找

若小于，则在前（左）半个区域继续进行折半查找
Step3 对确定的缩小区域再按折半公式，重复上述步骤。最后，得到结果：要么查找成功， 要么查找失败。
折半查找的存储结构采用一维数组存放。

折半查找算法举例

对给定数列（有序）{ 3，5，11，17，21，23，28，30，32，50}，按折半查找算法，查找关键字值为30的数据元素。

折半查找的算法讨论：

优点: ASL≤log2n，即每经过一次比较,查找范围就缩小一半。经log2n 次计较就可以完成查找过程。

缺点：因要求有序，所以要求查找数列必须有序，而对所有数据元素按大小排序是非常费时的操作。另外，顺序存储结构的插入、删除操作不便利。

考虑：能否通过一次比较抛弃更多的部分（即经过一次比较，使查找范围缩得更小），以达到提高效率的目的。……？

可以考虑把两种方法（顺序查找和折半查找）结合起来，即取顺序查找简单和折半查找高效之所长，来达到提高效率的目的？实际上这就是分块查找的算法思想。

例如：[问题分析] 由于数据按升序排列,故用折半查找最快捷.
program binsearch;
const max=10;
var num:array[1..max] of integer;
i,n:integer;
procere search(x,a,b:integer);
var mid:integer;
begin
if a=b then
if x=num[a] then writeln('Found:',a) else writeln('Number not found')
else begin
mid:=(a+b) div 2;
if x>num[mid] then search(x,mid,b);
if x<num[mid] then search(x,a,mid);
if x=num[mid] then writeln('Found:',mid);
end;
end;
begin
write('Please input 10 numbers in order:');
for i:=1 to max do read(num);
write('Please input the number to search:');
readln(n);
search(n,1,max);
end.

Java风格的代码举例：
//使用折半法进行查找
int getIndex(int[] nList, int nCount, int nCode) {
int nIndex = -1;
int jMin = 0;
int jMax = nCount - 1;
int jCur = (jMin+jMax)/2;
do
{
if(nList[jCur] > nCode) {
jMax--;
} else if(nList[jCur] < nCode) {
jMin++;
} else if(nList[jCur] == nCode) {
nIndex = jCur;
break;
}
jCur = (jMin + jMax)/2;
} while(jMin < jMax);

return nIndex;
}

二分查找的性能说明

虽然二分查找的效率高，但是要将表按关键字排序。而排序本身是一种很费时的运算。既使采用高效率的排序方法也要花费 O(n lg n) 的时间。
二分查找只适用顺序存储结构。为保持表的有序性，在顺序结构里插入和删除都必须移动大量的结点。因此，二分查找特别适用于那种一经建立就很少改动、而又经常需要查找的线性表。
对那些查找少而又经常需要改动的线性表，可采用链表作存储结构，进行顺序查找。链表上无法实现二分查找

二分查找的C#实现代码：
using System;
using System.Collections.Generic;
using System.Text;
namespace BinschDemo
{
public class BinschDemo
{
public static int Binsch(int[] a, int key)
{
int low = 1;
int high = a.Length;
while (low <= high)
{
int mid = (low + high) / 2;
if (key == a[mid])
{
return mid; //返回找到的索引值
}
else
{
if (key < a[mid])
high = mid - 1;
else
low = mid + 1;
}
}
return -1; //查找失败
}
static void Main(string[] args)
{
Console.WriteLine("请输入10个递增数字: ");
int[] list = new int[10];
for (int i = 0; i < 10; i++)
{
Console.Write("数字 : ", i);
list = Convert.ToInt32(Console.ReadLine());
}
Console.Write("请输入一个你要查找的数字:");
int find = Convert.ToInt32(Console.ReadLine());
int result = Binsch(list, find);
Console.WriteLine(result);
}
}
}

分块查找又索引查找，它主要用于“分块有序”表的查找。所谓“分块有序”是指将线性表L（一维数组）分成m个子表（要求每个子表的长度相等），且第i+1个子表中的每一个项目均大于第i个子表中的所有项目。“分块有序”表应该包括线性表L本身和分块的索引表A。因此，分块查找的关键在于建立索引表A。
（1）建立索引表A（二维数组）
索引表包括两部分：关键字项（子表中的最大值）和指针项（子表的第一项在线性表L中位置）
索引表按关键字有序的。
例如：线性表L（有序）为：1 2 3 4 5 6 7 8 9 10 11 12
分成m=3个子表：{1 2 3 4} {5 6 7 8} {9 10 11 12}
索引表A：二维数组：第一列为每个子表的最大值 ，第二列为每个子表的起始地址
即： 4 0
8 4
12 8
（2）利用索引表A，确定待查项X所在的子表（块）。
（3）在所确定的子表中可以用“折半查找”法搜索待查项X；若找到则输出X；否则输出未找到信息。

㈧ 分块查找(C语言)

i=idx[low1].low是块中第一个元素的起始位置的值

int blksearch(sqlist r,index idx,find=0,hb;) // bn为块个数 //
{ int i,;low=1,high1=bn,midl,find=0,hb;
while(low1<=high1&&!find)
{mid=(low1+high1)/2;
if(k<idx[mid1].key)high1=mid-1;
else if(k>idx[mid1],key)low1=mid1+1;
else{
low=mid1;
find=1;
}
到这里是初步锁定要查的元素在那个块，找到大的方向后 在块里进行进一步的搜索
if(low1<bn)//如果low1的值没有超过块的总个数
i=idx[low1].low; //i赋值为该块内第一个元素的起始位置
然后进一步查到元素

㈨ 查找算法的概念

用关键字标识一个数据元素，查找时根据给定的某个值，在表中确定一个关键字的值等于给定值的记录或数据元素。在计算机中进行查找的方法是根据表中的记录的组织结构确定的。顺序查找也称为线形查找，从数据结构线形表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于k的结点，表示查找失败。二分查找要求线形表中的结点按关键字值升序或降序排列，用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。分块查找也称为索引查找，把线形分成若干块，在每一块中的数据元素的存储顺序是任意的，但要求块与块之间须按关键字值的大小有序排列，还要建立一个按关键字值递增顺序排列的索引表，索引表中的一项对应线形表中的一块，索引项包括两个内容：① 键域存放相应块的最大关键字；② 链域存放指向本块第一个结点的指针。分块查找分两步进行，先确定待查找的结点属于哪一块，然后在块内查找结点。哈希表查找是通过对记录的关键字值进行运算，直接求出结点的地址，是关键字到地址的直接转换方法，不用反复比较。假设f包含n个结点，Ri为其中某个结点（1≤i≤n），keyi是其关键字值，在keyi与Ri的地址之间建立某种函数关系，可以通过这个函数把关键字值转换成相应结点的地址，有：addr(Ri)=H(keyi)，addr(Ri)为哈希函数。

㈩ 数组的冒泡排序和分块查找法

#include<iostream.h>

const int N=12,M=3;

void numbers (int a[]) //输入数组元素

{

cout<<"请输入"<<N<<"个元素"<<endl;

for(int i=0;i<N;i++)

cin>>a;

}

void sort(int a[],int n) //冒泡法排序

{

int t;

for(int i=0;i<n-1;i++)

for(int j=0;j<n-1-i;j++)

if(a[j]>a[j+1])

{

t=a[j];

a[j]=a[j+1];

a[j+1]=t;

}

}

void search(int a[]) //分块查找法

{

int x,j,i;

cout<<"请输入要查找的元素"<<endl;

cin>>x;

int b[N][2];

for(j=0,i=3;j<3,i<12;j++,i+=4)

b[j][0]=a;

for(j=0,i=0;j<3,i<12;j++,i+=4)

b[j][1]=i;

for(j=0;j<3;j++)

{

if(x<=b[j][0])

break;

}

if(x>a[N-1])

{

cout<<x<<" "<<"不在您要查找的数组中"<<endl;

return;

}

{

int top=b[j][1],bottom=b[j][1]+N/M-1,middle=(top+bottom)/2; //折半查找法

while(top<=bottom)

{

if(x==a[middle])

break;

else if(x>a[middle])

top=middle+1;

else

bottom=middle-1;

middle=(top+bottom)/2;

}

if(x==a[middle])

{

cout<<x<<" "<<"在您要查找的数组中"<<endl;

}

else

{

cout<<x<<" "<<"不在您要查找的数组中"<<endl;

}

}

}