高中二年級下學(xué)期信息科技《查找》教學(xué)課件

5.2查找5.2查找1、查找的意義信息學(xué)是處理大量信息的學(xué)科。除了對于收集到的信息轉(zhuǎn)為數(shù)據(jù)進行處理和存儲外，一個重要的需求就是對存儲的數(shù)據(jù)進行查找。日常生活中，我們就經(jīng)常進行查找工作，例如在圖書館中查找圖書、在字典中查找漢字等。如果將圖書目錄、字典等視作一張表，查找則是在一個含有眾多數(shù)據(jù)元素的表中找出某個特定的數(shù)據(jù)元素。在信息時代，由于信息量巨大，人工查找非常困難，因此需要依賴于計算機快速準確地查找信息5.2查找1、查找的意義順序表是指采用順序存儲的方式存儲的集合或線性表。本節(jié)所討論的兩種查找方法，均是針對一維數(shù)組這種順序表的查找方法。5.2查找2、順序查找順序查找又稱線性查找。順序查找的基本思想：

從順序表的一端開始，依次將每個元素的關(guān)鍵字與給定值k進行比較，如果相同，則查找成功，返回該元素的下標；如果所有元素比較后仍然找不到關(guān)鍵字為k的元素，則查找失敗，返回特定值-1。5.2查找2、順序查找例如，要實現(xiàn)查詢超市中某個商品在哪個貨架，可以用數(shù)組存儲商品的編號、存放的貨架等信息。程序運行時，輸入需查詢商品的編號，然后在數(shù)組中依次查找編號，即可根據(jù)編號對應(yīng)的下標提取出商品的信息。5.2查找2、順序查找intsearch(ShangPinTypea[],intk,intn){ //在有n個元素的數(shù)組a中查找編號k。 for(inti=0;i<n;i++) if(k==a[i].Bianhao)returni; //查找成功，返回商品對應(yīng)的數(shù)組下標。

return-1; //查找失敗，返回-1}5.2查找3、二分查找順序查找的思想易于理解，但其缺點也很明顯：

如果商品的數(shù)量過多，順序查找每次都需要在數(shù)組中從頭到尾依次查找，消耗大量時間。因此，為了加快查找的速度，可以使用另一種查找方式：二分查找。5.2查找3、二分查找二分查找，又稱折半查找。適用于順序存儲的有序表（各元素按關(guān)鍵字的值升序或降序存放的表）進行的查找。二分查找的思想：

利用有序表的有序性，每次將待查找元素所處的可能區(qū)間范圍縮小一半，以達到快速定位查找元素的目的。

通過每次比較當前范圍的中間元素與待查找元素的相對大小，可以確定待查找元素位于當前區(qū)間的左側(cè)還是右側(cè)。5.2查找3、二分查找以升序存儲的有序表a為例，二分查找的主要思路如下：（1）設(shè)定當前的查找范圍l=0,r=n-1。（2）選定查找范圍的中點元素mid=(l+r)/2，與k值比較

（a）若k==a[mid]，則查找成功，返回該元素的下標

（b）若k<a[mid]，則將范圍縮小到左子表a[l]~a[mid-1]

（c）若k>a[mid]，則將范圍縮小到右子表a[mid+1]~a[r]（3）迭代上述過程，直到找到k或當前查找區(qū)間為空（查找失?。?.2查找intbinsearch(ShangPinTypea[],intk,intn){ //在n個元素的升序表a中二分查找k intl=0,r=n-1; //初始化查找范圍的下界與上界 while(l<=r) //終止條件為查找范圍為空，即l>r { intmid=(l+r)/2; //取出中間元素下標 if(k==a[mid].BianHao)returnmid; //查找成功 elseif(k<a[mid].BianHao)r=mid-1; //如果沒有找到且編號偏小，則修改上界前往左子表 elsel=mid+1; //否則修改下界前往右子表。 } return-1; //查找范圍為空時仍未找到，則查找失敗。}5.2查找3、二分查找例：假設(shè)一維升序數(shù)組a中有10個元素：1,2,6,8,12,13,36,45,49,85?，F(xiàn)模擬查找k=45的二分查找過程：

下標：0123456789

元素：1268121336454985

LRMid5.2查找3、二分查找例：假設(shè)一維升序數(shù)組a中有10個元素：1,2,6,8,12,13,36,45,49,85。現(xiàn)模擬查找k=45的二分查找過程：

下標：0123456789

元素：1268121336454985

LRMidLMid5.2查找3、二分查找例：假設(shè)一維升序數(shù)組a中有10個元素：1,2,6,8,12,13,36,45,49,85?，F(xiàn)模擬查找k=48的二分查找過程：

下標：0123456789

元素：1268121336454985

LRMid5.2查找3、二分查找例：假設(shè)一維升序數(shù)組a中有10個元素：1,2,6,8,12,13,36,45,49,85。現(xiàn)模擬查找k=48的二分查找過程：

下標：0123456789

元素：1268121336454985

LRMidLMid5.2查找3、二分查找例：假設(shè)一維升序數(shù)組a中有10個元素：1,2,6,8,12,13,36,45,49,85。現(xiàn)模擬查找k=48的二分查找過程：

下標：0123456789

元素：1268121336454985

LRMidLMid5.2查找3、二分查找例：假設(shè)一維升序數(shù)組a中有10個元素：1,2,6,8,12,13,36,45,49,85?，F(xiàn)模擬查找k=48的二分查找過程：

下標：0123456789

元素：1268121336454985

LRL>R，查找失敗RMid5.2查找3、二分查找解決同一個問題，可以使用不同的算法編寫程序，從而對數(shù)據(jù)結(jié)構(gòu)有不同的要求。對比順序查找和二分查找：（1）數(shù)