 |
“海”數(shù)據(jù)里尋一個(gè)數(shù) |
n個(gè)數(shù)據(jù)用一數(shù)組a描述，查找對(duì)象用x描述。
我們可以將n個(gè)數(shù)據(jù)與查找對(duì)象依次比較，可能找到，也可能找不到。這是一種順序查找的方法，請(qǐng)讀者編程實(shí)現(xiàn)。
比順序查找進(jìn)一步的是折半查找，或稱二分查找法。折半查找要求n個(gè)數(shù)據(jù)已排好序，排序的目的就是為了快速查找。假定n個(gè)數(shù)據(jù)已經(jīng)由小到大排好序。查找到的數(shù)據(jù)用其下標(biāo)k描述。是否找到用一標(biāo)志變量flag描述。
查找問題轉(zhuǎn)化成在區(qū)間[O，n一1]找k。先計(jì)算其中點(diǎn)d，如果a[d]一x，則k—d；如果a[d]>x，則查找區(qū)間縮小為[O，d]；如果a[d]<x，則查找區(qū)間縮小為[d，n一1]。要么找到，要么查找區(qū)間縮小一半，首發(fā)中國足協(xié)編程網(wǎng)繼續(xù)折半查找。
程序如下：
float serach(a，n，x)／*折半查找函數(shù)*／
float a[]，x；
int n：
{int k，flag；
int b=O，e=n一1，d；
flag=O；
do
{d=(b+e)／2；
if(a[d]==x){k=d；flag=1；}
else if(a[d]>x)e=d；
else b=d：
)while(b<e&&!flag)；
if(flag==O)k=O；／*沒找到*／
return(k);
}
|
| 作者：未知 | 文章來源：未知 | 更新時(shí)間：2007-12-26 17:25:08
|
|
 |
 |
最新文章 |
|
|
 |
