Reference

顺序查找

# 顺序查找
def SequentialSearch(x, numList):
    count = 0
    for i in range(len(numList)):
        count += 1
        if x == numList[i]:
            return i, count
    return 0, 0  # 没有找到识别

折半/二分查找

# 非递归折半查找,应该针对顺序
def HalfSearch(x, numList):
    print(1)
    left = 0
    right = len(numList) - 1
    count = 0
    while right >= left:
        mid = int((right + left) / 2)
        if x > numList[mid]:
            left = mid+ 1
            count += 1
        elif x < numList[mid]:
            right = mid- 1
            count += 1
        else:
            return mid, count
    return 0, 0 # 没找到

分块查找

  • 对于不增长的数据来说，使用二分是足够的，但是如果数据一直在改变，每次都先进行排序则大大增加了复杂度，因此可采用分块的形式

三分查找

  • 发现三分是有两种情况的，网上很多是说找最值，但是其实也可以是三等分的查找
# 三等分查找
def TernarySearch(x, numList):
    print(3)
    left = 0
    right = len(numList) - 1
    count = 0
    while right >= left:
        leftMid = int((right - left) / 3) + left
        rightMid = int((right - left) * 2 / 3) + left
        leftValue = numList[leftMid]
        rightValue = numList[rightMid]
        if x == leftValue:
            count += 1
            return leftMid, count
        elif x == rightValue:
            count += 1
            return rightMid, count
        if leftValue > x:
            count += 1
            right = leftMid - 1
        elif leftValue < x < rightValue:
            count += 1
            left = leftMid + 1
            right = rightMid - 1
        elif x > rightValue:
            count += 1
            left = rightMid + 1
    return 0, 0 # 没找到

插值查找

  • 借助数学公式的查找，算是二分的优化
def formula(l, r, key, numList):
    p = (key - numList[l]) / (numList[r] - numList[l])
    n = r - l
    idx = int(n * p)
    return idx


def interpolation_search(x, numList):
    l = 0
    r = len(numList) - 1
    while l < r:
        expect = l + formula(l, r, x, numList)
        expect = max(l, min(expect, r))
        if numList[expect] == x:
            return expect
        elif numList[expect] < x:
            l = expect + 1
        else:
            r = expect - 1
    return -1

快速查找(递归)

减可变规模的查找

# 减可变规模Decrease and Conquer
def DCpartition(numList, start, end):
    p = numList[start]  # 默认将第一个作为中轴,并且保存该值，第一个值空缺
    m = start  # 空缺位置
    for i in range(start + 1, end):
        if numList[i] < p:
            m += 1
            numList[m], numList[i] = numList[i], numList[m]

    numList[start], numList[m] = numList[m], numList[start]
    return m


def QuickSelect(k, numList, start, end):
    m = DCpartition(numList, start, end)  # 根据数列的第一个元素作为中轴分组
    re = start + k - 1  # 用来判断分组的中轴值是不是就是我们想要的第k个元素
    if m == re:  # 是第k个元素
        return m  # 返回第k个最小值元素的坐标
    elif m > re:
        # 答案在左子数列
        return QuickSelect(k, numList, start, m)
    else:
        # 答案在右子数列
        return QuickSelect(re - m, numList, m + 1, end)