人工智能基礎(chǔ)算法之查找算法

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

順序查找

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

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

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

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

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

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

二分查找

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

二分查找代碼實(shí)現(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

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

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

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

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

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

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

插值查找

插值查找(lnterpolation Search)是對(duì)實(shí)例的二分查找的改進(jìn)，其應(yīng)用場(chǎng)景是排序數(shù)組中的值是均勻分布的。二分查找總是到中間元素做左右劃分，而插值搜索會(huì)根據(jù)正在搜索的Key的大小來(lái)確定劃分的位置例如，如果Key更接近最后一個(gè)元素，則插值搜索會(huì)從后半部分開始進(jìn)行數(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

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

分塊查找

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

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

分塊查找查找過(guò)程：

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

②在塊內(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]的單獨(dú)分塊
        key[1] = len(subList)
        sortList += subList
        iList=list（set（iList）- set（subList））#過(guò)濾掉已經(jīng)加入到subList中的元素
    ilist = sortlist
    return indexList

def blockSearch(iList, key, indexList):
    left = 0 #搜索數(shù)列的起始點(diǎn)索引
    right=e#搜索數(shù)列的終點(diǎn)索引
    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