查找算法是什么？查找算法如何實現(xiàn)

查找算法也可以叫搜索算法。查找算法就是從一個有序數(shù)列中找出一個特定的數(shù)，常用于判斷某個數(shù)是否在數(shù)列中，或者某個數(shù)在數(shù)列中的位置。在計算機應(yīng)用中，查找是常用的基本運算，是算法的重要組成部分。下面來看算法中的順序查找、二分查找、插值查找和分塊查找，介紹他們的實現(xiàn)方法。

順序查找

順序查找(也被稱為線性查找)是最簡單、最直接的查找算法。顧名思義，順序查找就是將數(shù)列從頭到尾按照順序查找一遍，是最容易理解的算法。

舉例：我們要從下面數(shù)列中找到“1”這個元素。

我們要從下面數(shù)列中找到“1”這個元素，從第一個元素開始遍歷，逐一比較。

我們要從下面數(shù)列中找到“1”這個元素，從第一個元素開始遍歷，逐一比較，直到找到(或遍歷完成)為止。

def sequentialSearch(ilist, key):
    iLen = len(iList)
    for i in range(iLen):
        if ilist[i] == key:
          return i
    return -1

順查找的時間復(fù)雜度O(n)，空間復(fù)雜度0(1)。

二分查找

(Binary Search)是應(yīng)用在有序數(shù)據(jù)中的，十分高效的查找算法。如果數(shù)據(jù)是無序的，我們先要將數(shù)據(jù)從小到大排序。其原理是比較待查數(shù)據(jù)與數(shù)組中值的數(shù)據(jù)的大小，如果等于中間值則直接返回，如果大于中間值，就只在后半部分查找，如果小于中間值，就在前半部分查找，如此往復(fù)，直到找到數(shù)據(jù)，或剩下一個元素。

二分查找代碼實現(xiàn)

def binary_search(iList, key):
    iLen = len(iList)
    left = 0
    right = iLen -1
    while right - left > 1:
        mid = (left + right) // 2
        if key < ilist[mid]:
          right = mid
        elif key > ilist[mid]:
            left = mid
        else:
          return mid
    if key == iList[left]:
        return left
    elif key == ilist[right]:
        return right
    else:
      return -1

二分查找的時間復(fù)雜度是o(logn)

①在n個元素中尋找→②在n/2個元素中尋找→③在n/4個元素中尋找….在1個元素中尋找

n經(jīng)過幾次“2”=1→log2n=0(logn)

搜索過程從數(shù)組的中間元素開始，如果中間元素正好是要查找的元素，則搜索過程結(jié)束。如果某一特定元素大于或者小于中間元素，則在數(shù)組大于或小于中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。

如果在某一步驟數(shù)組為空，則代表找不到。這種搜索算法每一次比較都使搜索范圍縮小一半。

二分查找的時間復(fù)雜度：0(logn)

插值查找

插值查找(lnterpolation Search)是對實例的二分查找的改進，其應(yīng)用場景是排序數(shù)組中的值是均勻分布的。二分查找總是到中間元素做左右劃分，而插值搜索會根據(jù)正在搜索的Key的大小來確定劃分的位置例如，如果Key更接近最后一個元素，則插值搜索會從后半部分開始進行數(shù)據(jù)劃分。

Mid =L + (R-L) x (target–data[L]) / data[R]-data[L]

插值查找舉例：

Mid = L +(R-L)(target- data[L]) / data[R]-data[L]= 0+(7-0) ×(11-1)÷(14-1) =7× 10÷13 = 5.38

插值查找代碼

def interpolation_search(ilist, key):
    iLen = len(iList)
    left = 0
    right = iLen - 1

    while right - left > 1:
        mid = left + (key -iList[left]) * (right - left) // (iList[right] - iList[left])
        if mid == left:
            mid +=1  # 當(dāng)ilist[right]和ilist[left]相差太大,有可能導(dǎo)致mid一直等于left陷入死循環(huán)
        if key < iList[mid]:
            right = mid
        elif key > ilist[mid]:
            left = mid
        else:
          return mid
    if key == ilist[left]:
        return left
    elif key == iList[right]:
        return right
    else:
        return -1

二分查找的改進，適合均勻分布的有序數(shù)組插值查找算法的復(fù)雜度是0(loglogn)。

分塊查找

分塊查找和以上幾種查找方式有所不同：順序查找的數(shù)列是可以無序的;二分法查找和插入查找的數(shù)列必須是有序的;分塊查找介于兩者之間，需要塊有序，元素可以無序。

分塊查找，先按照一定的取值范圍將數(shù)列分成數(shù)塊。塊內(nèi)的元素是可以無序的，但塊必須是有序的。所謂塊有序，就是處于后面位置的塊中的最小元素都要比前面位置塊中的最大元素大。

分塊查找查找過程：

①確定待查記錄所在塊(順序或折半查找)

②在塊內(nèi)查找(順序查找)

iList = randomList(20)
indexList = [[250, 0], [500, 0], [750, 0], [1000, 0]]

def divideBlock():
    global ilist, indexlist
    sortList = []
    for key in indexList:
        subList = [i for iin iList if i<key[e]]#列表推導(dǎo)，小于key[e]的單獨分塊
        key[1] = len(subList)
        sortList += subList
        iList=list（set（iList）- set（subList））#過濾掉已經(jīng)加入到subList中的元素
    ilist = sortlist
    return indexList

def blockSearch(iList, key, indexList):
    left = 0 #搜索數(shù)列的起始點索引
    right=e#搜索數(shù)列的終點索引
    for indexInfo in indexList:
        if(left+right)<len(iList):
          left += right
        right += indexInfo[1]
        if key < indexInfo[0]:
            break
    for i in range(left, right):
        if key == ilist[i]:
            return i
    return -1