順序和減半發現 20

順序查詢方法。

假設：num（i） 是學生的學號，nam$（i） 是姓名，num 是搜尋物件。

sub search

for i=1 to n

if num=num(i) then

print "num";num(i)

print "name";nam$(i)

exit for

end if

next i

if i>n then num ;"not found"

end sub

半搜尋法（二元搜尋法）;

檢索按一定規則排列的資料（從小到大或從大到小）; 假設：num（i） 是學生的學號，按降序排列，nam$（i） 是姓名，num 是搜尋物件。

sub search

top=1bot=n

find=0

do mid=int((top+bot)/2)if num=num(mid) then

print "num";num(i)

print "name";nam$(i)

find=1

elseif num bot=mid-1

elseif num>num(mid) thentop=mid+1

end if

loop until ((botif find=0 then num ;"not found"

end sub

1. 首先，確定整個搜尋間隔的中間位置 mid=（ left + right） 2 .

2、將要檢查的關鍵詞值與中間位置的關鍵詞值進行比較; 如果相等，則搜尋成功，如果大於，則在區域的後（右）半部分繼續減半，如果小於，則在區域的前（左）底半部分繼續減半。

3.根據確定的減少面積減半的公式重複上述步驟。 結果是結束：要麼搜尋成功，要麼搜尋失敗。 半折搜尋的儲存結構儲存在一維陣列中。

C++的語言特點：

1.支援資料封裝和資料隱藏。

在 C++ 中，類是支援資料封裝的工具，物件是資料檔案延遲封裝的實現。 C++ 通過建立使用者定義的類來支援資料封裝和資料隱藏。

在物件導向的程式設計中，合法操作的資料和函式被封裝為類定義。 物件被描述為具有給定類的變數。 每個給定類的物件都包含該類指定的許多私有、公共和受保護成員。

一旦建立了乙個定義良好的類，就可以將其視為乙個完全封裝的實體，可以用作整體單元。 類的實際內部工作是隱藏的，具有明確定義的類的使用者不需要知道類是如何工作的，只需要知道如何使用它。

2.支援繼承和復用。

新型別可以在 C++ 中的現有類之上宣告，這就是繼承和重用的思想。 繼承和重用可以幫助您更有效地組織程式結構，明確類之間的關係，並充分利用現有類進行更複雜和更深入的開發。 新定義的類是乙個子類，並成為派生類。

它可以從父類繼承所有非私有屬性和方法作為自己的成員。

3.支援多型性。

多型性用於指定每個類的效能行為。 多型性形成乙個由父類及其子類組成的樹狀結構。 此樹中的每個子類都可以接收一條或多條具有相同名稱的訊息。

當樹中某個類的物件接收到訊息時，該物件會動態確定給定給子類物件的訊息的某種用法。 多型性的這一特性允許使用高階抽象。

繼承和多型性的結合使得生成一系列相似但唯一的物件變得容易。 由於繼承，這些物件具有許多相似的特徵。 由於多型性，乙個物件可以具有獨特的行為方式，而另乙個物件可以具有另一種行為方式。

搜尋過程從陣列的中間元素開始，如果中間元素恰好是要找到的元素，則結束; 如果某個特定元素大於或小於中間元素，則在陣列中大於或小於中間元素的一半中找到該元素，並且比較從中間元素開始時開始。 如果陣列在某個步驟中為空，則找不到它。 這種搜尋演算法在每次比較時將搜尋範圍縮小到一半。

折半搜尋方法是一種更有效的搜尋方法。 其優點是比較成功的公告數量少，搜尋速度快，平均效能好; 缺點是要求要查詢的表是有序表，插入和刪除困難。 因此，半折搜尋方法適用於查詢不經常變化的有序列表並經常查詢它們。

“半查詢方法”的步驟說明：

1. 首先，確定整個搜尋間隔的中間位置 mid=（ left + right） 2 .

2）將待檢查關鍵字的值與中間位置的關鍵字值進行比較;如果相等，則搜尋成功; 如果它更大，則搜尋將繼續在後（右）半區域減半; 如果小於此值，則在該區域的前（左）半部分繼續進行半折搜尋。

3.根據確定的減少面積減半的公式重複上述步驟。 結果是結束：要麼搜尋成功，要麼搜尋失敗。 半折搜尋的儲存結構儲存在一維陣列中。

以上內容參考：百科全書-半搜尋方法。

至少 50 次關閉，60 次成功查詢。

首先，假設表中的元素是按公升序排列的，將表中間記錄的關鍵字與查詢關鍵字進行比較，如果兩者相等，則查詢成功。 否則，使用中間位置記錄將表劃分為兩個子表，第乙個子表和最後乙個子表，如果中間位置記錄的關鍵字大於搜尋關鍵字，則進一步搜尋前乙個子表，否則進一步搜尋下乙個子表。

重複上述過程，直到找到滿足條件的記錄，使查詢成功，或者直到子表不存在，在這種情況下，查詢不成功。

基本思想是將 n 個元素分成兩半，數量大致相同（假設陣列元素按公升序排列），將 a[n 2] 與要查詢的 x 進行比較，如果 x=a[n 2]，則找到 x，演算法終止; 如果 xa[n 2]，那麼我們只需要繼續在陣列 a 的右半部分搜尋 x。

半折檢查和搜尋可以在二叉樹的幫助下進行描述。

為了簡化討論，我們把樹近似為乙個完整的二叉樹，讓二叉樹的高度為 h（h>1）。

然後，根據二叉樹的性質，它旁邊有乙個最大數量的節點 n=2 h-1，則 h=log2（n+1） （2 是基數）。 那麼二叉樹j層的節點數為：2（j-1）。

假設每個元素的找到概率相等，那麼，pi = 1 n（pi 是第 i 個節點的找到概率）。

則平均查詢長度為 1 n*（1*2 0+2*2 1+3*2 2+......j*2^(j-1)）

平均搜尋長度如下：（（n+1） n ） log2（n+1）-1（其中對數中的 2 為底：即以 2 為底數 （n+1）） 的對數）。

注意：當 n 較大時，可以近似為 log2（n+1）-1

搜尋過程從陣列的中間元素開始，如果中間元素恰好是要找到的元素，則結束; 如果特定元素大於或小於中間元素，則在陣列中大於或小於中間元素的一半中找到該元素。

1.順序查詢。

常規線性表的順序查詢：

從線性表的一端開始，逐個檢查關鍵字是否符合給定條件。 如果發現某個元素的關鍵字滿足給定條件，則搜尋成功，並返回該元素的 ** 表中的位置。 如果已找到表的另一端，但未找到與給定條件匹配的元素，則返回有關搜尋失敗的訊息。

有序表的順序查詢：

假設表L按關鍵詞從小到大排序，搜尋順序從上到下，要搜尋的元素的關鍵詞是key。 找到第i個元素時，發現第i個元素對應的關鍵字小於該鍵，但i+1元素對應的關鍵字大於該鍵，可以返回搜尋失敗訊息。

2.對折找到。

也稱為二分查詢，它僅適用於有序的順序表。

首先，將給定的值鍵與表中間的元素進行比對，如果相等，則搜尋成功，返回元素的儲存位置。 如果沒有，您需要查詢的元素只能位於中間元素的前半部分或後半部分。 然後在較窄的範圍內繼續相同的搜尋，依此類推，直到找到它。

或者，如果表中沒有需要查詢的元素，則搜尋將失敗，並返回有關搜尋失敗的訊息。

3.磁貼搜尋。

又稱索引順序搜尋，它借鑑了順序搜尋和摺疊半搜尋的優點，既有動態結構，又適合快速搜尋。

將查詢表劃分為多個子塊。 塊中的元素可以是無序的，但塊之間是有序的，第乙個塊中最大的關鍵字小於第二個塊中所有記錄的關鍵字，依此類推。 然後建立索引表，索引表中的每個元素包含每個塊的最大關鍵字和每個塊中第乙個元素的位址，索引表按關鍵字順序排列。

半折搜尋法是一種效率高的搜尋方法，假設有五個整數a0 a4按從小到大的順序進行判斷和修正，用空格求到的數字是x，其基本思想是：

設搜尋資料範圍的下限為l=0，上限為h=4，求中點m=（l+h）2，將x與中點元素am進行比較，如果x等於am，即找到它，停止搜尋。

否則，如果 x 大於 am，則替換下限 l=m+1 並繼續在下半部分搜尋。

如果 x 小於 am，則更改上限 h=m-1，前半部分繼續講盲搜，重複前面的過程，直到找到或 l>h。

如果 l>h，則表示沒有這樣的數字，列印找不到資訊，程式結束。

這種方法不斷將搜尋範圍縮小一半，因此搜尋效率很高。