线性表的查找

# 0、生产一个随机数组、正序
import random
lista = [x for x in range(0, 30)]  # 生成一个列表
listA = sorted(random.sample(lista, 10))  # 从中随机抽取10个作为待查找列表
print(listA)
tagval = 16  # 目标值
# 1、顺序查找：遍历
def one(tag, slist):
    for i, em in enumerate(slist):
        if tag == em:
            return i, em
    return -1, None
# 2、二分查找：二分法
def two(tag, slist):
    start = 0
    end = len(slist) - 1
    while start <= end:
        middle = int((end + start)/2)
        if tag == slist[middle]:
            return middle, slist[middle]
        elif tag < slist[middle]:
            end = middle - 1
        else:
            start = middle + 1
    return -1, None
# 2.1、支持重复元素的二分查找
def twoo(tag, slist):
    result = []
    start = 0
    end = len(slist) - 1
    while start <= end:
        middle = int((end + start) / 2)
        if tag == slist[middle]:
            if middle > 0 and slist[middle-1] == tag:  # 看前一个元素是否＝目标元素
                for id in range(middle-1, -1, -1):
                    if slist[id] == tag:
                        result.append(id)
            if middle < end and slist[middle+1] == tag:  # 看后一个元素是否＝目标元素
                for id in range(middle+1, end):
                    if slist[id] == tag:
                        result.append(id)
            result.append(middle)
            return result
        elif tag < slist[middle]:
            end = middle - 1
        else:
            start = middle + 1
    return -1
print(one(tagval, listA))
print(two(tagval, listA))