順序查找和折半查找
摘要：本篇文章中，主要講述了在資料結構中涉及的幾大查找演算法，包括：線性結構、樹形結構和散列結構及演算法的效率指標，這些查找方式都是資料結構中最基本的查找方式，并且在資料結構中運用很廣泛，合適的使用對應的查找演算法，不僅能夠提高演算法操作效率，還能夠節省查找時間，下述便先來談談查找演算法中的基于線性結構的順序查找演算法和折半查找演算法，
知識框架:
一、查找的基本概念
1、查找：在資料集合中尋找滿足某種條件的資料元素的程序稱為查找，查找的結果一般分為兩種：查找成功（在資料集合中找到了滿足條件的資料元素）、查找失敗，
2、查找表(查找結構)：用于查找的資料集合稱為查找表，由同一型別的資料元素組成，可以是一個陣列或鏈表等資料型別，對查找表經常進行的操作一般有如下四種：
（1）查詢某個特定的資料元素是否在查找表中
（2）檢索滿足條件的某個特定的資料元素
（3）在查找表中插入一個資料元素
（4）從查找表中洗掉某個資料元素
注：(1)、(2)類查找表稱為靜態查找表；(3)、(4)類為動態查找表；靜態查找表與動態查找表的區別在于：靜態查找表只是查看滿足某一條件的資料元素是否在表中，在就回傳true，否則回傳false,不做其它操作；而動態查找表則是在表中查詢這個資料元素，如果不存在則插入這個資料元素，否者洗掉這個資料元素，
3、查找表的查找方法
（1）靜態查找表：順序查找、折半查找、散列查找等，
（2）動態查找表：二叉排序樹查找、散列查找，
4、關鍵字：在資料元素中唯一標識該元素的某個資料項的值，使用基于關鍵字的查找，查找結構應該是唯一的，如一個學生元素構成的資料集合中，學生元素中“學號”這一個資料項的值唯一地表示一名學生，
5、平均查找長度：在查找程序中，一次查找的長度是指需要比較的關鍵字次數，而平均查找長度則是所有查找程序中進行關鍵字的比較次數的平均值，
二、順序查找和折半查找
1、順序查找
（1）概念：主要在線性表中進行查找，順序查找通常分為對一般的無序線性表（無序表）的順序查找和對按關鍵字有序的順序表（有序表）的順序查找，
（2）基本思想：從線性表的一端開始，逐個檢查表中的關鍵字是否滿足給定條件，若找到，則查找成功，并且回傳該關鍵字在線性表中的位置，若已查找到表的另一端，但沒有找到符合給定條件的元素，則回傳失敗的資訊，
（3）哨兵的作用：順序查找程序中引入“哨兵”的作用：主要是為了判斷在查找程序中陣列是否越界，同時引入“哨兵”還可以避免很多不必要的判斷陳述句，提高程式效率，
（4）平均查找長度：在順序查找的程序中時，對于有n個資料元素的資料集合中，給定值key與表中第 i 個元素相等，即定位第 i 個元素時，需要進行 n-i+1 次關鍵字的比較，即有：C= n-i+1，查找成功時，順序查找的平均長度為：(n+1)/2；查找不成功時，與表中的各個關鍵字的比較次數是 n+1 次，從而順序查找不成功的平均查找長度為：n+1，
2、折半查找
（1）折半查找又叫二分查找，僅用于有序順序表，
（2）基本思想：首先將給定值key與表中間位置的元素比較，若相等，則查找成功，回傳該元素的存盤位置，若不等，則所需查找的元素只能在中間元素以外的前半部分或后半部分進行折半查找，依次重復如此步驟，直到找到為止，或確定表中沒有所需要查找的元素，則查找失敗，回傳查找失敗的資訊，
（3）折半查找操作程序：
初始：i=0，j=n-1，mid=(i+j)/2=(0+n-1)/2=（n-1)/2
第一種情況：
key>（n-1)/2，則：i=mid+1，j=n-1,mid=(i+j)/2
第二種情況：
key<（n-1)/2，則：i=0，j=mid-1,mid=(i+j)/2
注：若 i>j，則查找不成功，
（4）折半查找程序可用二叉樹來描述，又叫判定樹，
- 查找成功時的平均查找長度為從根結點到目的結點的結點數；
- 查找失敗時的查找長度為從根結點到對應失敗結點的父結點的路徑上的結點樹，
- 用折半查找法查找給定值的比較次數最多不超過樹的高度，
- 查找成功：根結點—>目的結點的結點數
- 查找失敗：根結點—>對應失敗結點的父結點的結點數
注：每個結點值均大于其左子結點值，且均小于其右子結點值，因此，判定樹是一顆平衡二叉樹，
（5）平均查找長度：在等概率查找時，查找成功的平均查找長度：ASL=log2(n+1)-1
注：折半查找的時間復雜度：O(log2n)
3.分塊查找
（1）分塊查找又稱為索引順序查找，吸取了順序查找和折半查找各自的優點，既有動態查找，又適于快速查找，
（2）基本思想：將查找表分為若干子塊，塊內元素可以無序，但塊間必須有序，即第一個塊中的最大關鍵字小于第二個塊中的所有記錄的關鍵字，第二個塊中的最大關鍵字小于第三個塊中的所有記錄的關鍵字，以此類推，再建立一個索引表，索引表中每個元素含有各塊的最大關鍵字和各塊中第一個元素的地址，索引表按關鍵字有序排列，
（3）分塊查找的程序有兩步：在索引表中確定待查記錄所在的塊，可以順序查找或折半查找；在塊內順序查找，
（4）平均查找長度：將長度為n的查找表均勻分為b塊，每塊含有s個記錄，在等概率的情況下，若在塊內和索引表中均采用順序查找，則平均查找長度為：
- 平均查找長度：ASL=L1+L2=(b+1)/2+(s+1)/2=(s2+2s+n)/2s
若采用折半查找時，則平均查找長度為：
- ASL=L1+L2=(s+1)/2+log(b+1)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/272358.html
標籤：其他
上一篇：資料結構基礎知識（持續更新中）