分塊查找演算法

㈠ 分塊查找演算法中如何對數據分塊

可以實現確定待查找數據的上限和下限，
然後對該區間等分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;

}

}

}