查找

在計算機科學中定義為：在一些（有序的/無序的）數據元素中，通過一定的方法找出與給定關鍵字相同的數據元素的過程叫做查找。也就是根據給定的某個值，在查找表中確定一個關鍵字等於給定值的記錄或數據元素。

基本介紹

• 中文名：查找
• 拼音：cházhǎo
• 英譯：[search for;scour]
• 解釋：徹底考查或搜尋

漢語詞語

【詞目】查找

【拼音】cházhǎo

【英譯】[search for;scour]

【釋義】徹底考查或搜尋

【示例】查找檔案。

信息技術名詞

在計算機科學中定義為：在一些（有序的/無序的）數據元素中，通過一定的方法找出與給定關鍵字相同的數據元素的過程叫做查找。也就是根據給定的某個值，在查找表中確定一個關鍵字等於給定值的記錄或數據元素。

Windows 日記本的一個功能，可用於搜尋便箋檔案。

英文詞組：look up

網頁和檔案中使用ctrl+f彈出查找框 輸入要查找的文字即可找到查找項

計算機算法

順序查找

⒈順序查找的思想是：

將查找值順序逐個與結點值進行比較，相等即為查找成功，否則查找失敗.

程式（Pascal）如下：

program sxcz;

const n=7;

type

arr=array[1..n] of integer;

var x1,i:integer;

a:arr;

b:boolean;

place:integer;

procedure search(r:arr;m,x:integer; var found:boolean;var p:integer);

begin

p:=1;found:=false;

while(p<=m) and not found do

if r[p]=x then found:=true else p:=p+1;

end;

begin

write('Enter array:');

for i:=1 to n do read(a[i]);

writeln;

write('Enter search data:');

read(x1）；

search(a,n,x1,b,place);

if b then begin writeln('yes');writeln('Place of',x1:5,'is:',place); end

else writeln('no');

end.

二分查找

⒈二分查找的基本思想：首先將結點按關鍵字排序，其次將查找值與中間位置的值比較，相等，查找成功；不等，則中間數據大於或小於查找值，無論怎樣查找將在一半的數據中查找。

⒉例：輸入序列數據查找指定值.

程式（Pascal）：

program sxcz;

const n=7;

type

arr=array[1..n] of integer;

var x1,i:integer;

a:arr;

place:integer;

procedure paixv(var r:arr;m:integer);

var k,j,i,t:integer;

begin

k:=m;

while k>0 do

begin

j:=k-1;k:=0;

for i:=1 to j do

if r[i]>r[i+1] then

begin t:=r[i];a[i]:=r[i+1];r[i+1]:=t;k:=i;end;

end;

end;

procedure search(r:arr;m,x:integer; var p:integer);

var low,high,mid:integer;

begin

p:=0;low:=1;high:=m;

while low<=high do

begin

mid:=(low+high) div 2;

if x>r[mid] then low:=mid+1 else

if x<r[mid] then high:=mid-1 else

begin p:=mid;exit;end;

end;

end;

begin

write('Enter array:');

for i:=1 to n do read(a[i]);

writeln;

write('Enter search data:');

read(x1）；

paixv(a,n);

search(a,n,x1,place);

if place<>0 then writeln('yes') else writeln('no');

end.

二叉排序樹查找

因為二叉排序樹的左子樹若不為空則左子樹的所有結點的值均小於它的根結點的值，而右子樹若不為空，則右子樹的所有結點的值均不小大於它的根結點的值，根據這個性質查找算法如下（Pascal）：

program pxtree;

const

a:array[1..8] of integer=（10,18,3,8,12,2,7,3）；

type point=^nod;

nod=record

w:integer;

right,left:point ;

end;

var root,first:point;k:boolean;i,x:integer;

procedure maketr(d:integer;var p:point);

begin

if p=nil then

begin

new(p);

with p^ do begin w:=d;right:=nil;left:=nil end;

if k then begin root:=p; k:=false end;

end

else with p^ do if d>=w then maketr(d,right) else maketr(d,left);

end;

function searchtr(x:integer;p:point):boolean;

begin

if p=nil then searchtr:=false

else if x=p^.w then searchtr:=true

else if x<p^.w then searchtr:=searchtr(x,p^.left)

else searchtr:=searchtr(x,p^.right);

end;

begin

first:=nil;k:=true;

for i:=1 to 8 do maketr(a[i],first);

write('want find data x:');read(x);

if searchtr(x,first) then writeln('yes') else writeln('No');

end.

哈希（Hash）表

以上講的查找方法基於比較的，查找效率依賴比較次數，其實理想的查找希望不經比較，一次存取便能得到所查記錄，那就必須在記錄的存儲位置和它的關鍵字之間建立一個確定的對應關係f，這樣查找k時，只要根據這個對應關係f找到給定值k的像f(k）。這種對應關係f叫哈希（hash）函式。按這種思想建立的表叫哈希表（也叫散列表）。哈希表存取方便但存儲時容易衝突（collision）：即不同的關鍵字可以對應同一哈希地址。如何確定哈希函式和解決衝突是關鍵。

⒈哈希函式的構造方法

直接定址法：H(k)=k 或H(k)=a*k+b（線形函式）

如：人口數字統計表

地址	1	2	3	...	100
年齡	1	2	3	...	100
人數	67	3533	244	...	4

數字分析法：取關鍵字的若干數位組成哈希地址

如：關鍵字如下：若哈希表長為100則可取中間兩位10進制數作為哈希地址。

81346532

81372242

81387422

81301367

81322817

81338967

81354157

81368537

平方取中法：關鍵字平方後取中間幾位數組成哈希地址

摺疊法：將關鍵數字分割成位數相同的幾部分（最後一部分的位數可以不同）然後取幾部分的疊加和（捨去進位）作為哈希地址。

除留餘數法：取關鍵字被某個不大於表長m的數p除後所得的餘數為哈希地址。

H(k)=k mod p p<=m

隨機數法：H(k)=rondom(k）。

⒉處理衝突的方法

假設地址集為0..n-1，由關鍵字得到的哈希地址為j(0<=j<=n-1）的位置已存有記錄，處理衝突就是為該關鍵字的記錄找到另一個"空"的哈希地址。在處理中可能得到一個地址序列Hi i=1，2，...k

0<=Hi<=n-1），即在處理衝突時若得到的另一個哈希地址H1仍發生衝突，再求下一地址H2，若仍衝突，再求H3...。怎樣得到Hi呢？

開放定址法：Hi=(H(k)+di) mod m （H(k）為哈希函式；m為哈希表長；di為增量序列）

當di=1，2，3，... m-1 時叫線性探測再散列。

當di=1，-1，2，-2，3，-3，...,k,-k時叫二次探測再散列。

當di=random（m）時叫偽隨機探測序列。

例：長度為11的哈希表關鍵字分別為17，60，29，哈希函式為H(k)=k mod 11，第四個記錄的關鍵字為38，分別按上述方法添入哈希表的地址為8，4，3（隨機數=9）。

再哈希法：Hi=RHi(key) i=1,2,...,k，其中RHi均為不同的哈希函式。

鏈地址法：這種方法很象基數排序，相同的地址的關鍵字值均鏈入對應的鍊表中。

建立公益區法：另設一個溢出表，不管得到的哈希地址如何，一旦發生衝突，都填入溢出表。

⒊哈希表的查找

例：如下一組關鍵字按哈希函式H(k)=k mod 13和線性探測處理衝突所得的哈希表a[0..15]:

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
	14	01	68	27	55	19	20	84	79	23	11	10

當給定值k=84，則首先和a[6]比在依次和a[7],a[8]比結果a[8]=84查找成功。

當給定值k=38，則首先和a[12]比，再和a[13]比，由於a[13]沒有，查找不成功，表中不存在關鍵字等於38的記錄。

查找第k小元素

查找第k小元素即在n個元素中（未排序）找到第k小的元素。方法同快速排序，採用遞歸方式。

程式如下（Pascal）：

program kspv;

const n=7;

type

arr=array[1..n] of integer;

var

b:arr;

i,k:integer;

function p(s,t:integer):integer;

var i,j,t1,x:integer;

begin

i:=s;j:=t;x:=b[i];

repeat

while (b[j]>=x) and (j>i) do j:=j-1;

if j>i then begin t1:=b[i]; b[i]:=b[j];b[j]:=t1;end;

while (b[i]<=x) and (i<j) do i:=i+1;

if i<j then begin t1:=b[j];b[j]:=b[i];b[i]:=t1; end

until i=j;

b[i]:=x;

p:=i;

end;

function find(s,t,k:integer):integer;

var p1,q:integer;

begin

if s=t then find:=b[s] else

begin

p1:=p(s,t);

q:=p1-s+1;

if k<=q then find:=find(s,p1,k) else find:=find(p1+1,t,k-q);

end;

end;

begin

write('input data:');

for i:=1 to n do read(b[i]);readln;

write('input k:');read(k);

write('output data:');

writeln('kthsmall:=',find（1,n,k));

end.