【python&顺序查找算法、二分查找算法、二分法查找的递归解法】

• • 顺序查找算法
  • 二分查找算法
  • 二分法查找的递归解法

顺序查找算法

# 顺序查找项，并输出其索引

def sequentialSearch(list,item):
    pos = 0
    found = False
    # 按照索引持续对比查找
    while pos < len(list)  and not found:
          # 对比找到索引项
        if list[pos] == item:
            found = True
        else:
            # 否则，顺序增长 下标
            pos = pos + 1
    return found,pos

testlist = [1,2,3,4,5,6,78,54,32,11,0]
item = 11
res = sequentialSearch(testlist,item)


print("在%s中查找%s，%s，并且其索引值为：%s" %(testlist,item,res[0],res[1]))

结果：

在[1, 2, 3, 4, 5, 6, 78, 54, 32, 11, 0]中查找11，True，并且其索引值为：9

二分查找算法

# 二分法查找  binarySearch
def function(list,item):
    first = 0
    last = len(list)-1
    found = False
    while first <= last and  not found:
        midpoint = (first + last)//2
        if midpoint == item:
            found = True
        else:
            if item < list[midpoint]:
                last = midpoint - 1
            else:
                first = midpoint  + 1
       
    return found


list= [1,2,3,4,5,6,7,8,9,10,11]
print(function(list,6))

结果：

True

二分法查找的递归解法

def binarySearch(list,item):
    if len(list) == 0:
        return False
    else:
        midpoint = len(list)//2
        if list[midpoint] == item:
            return True
        else:
            if item < list[midpoint]:
                return binarySearch(list[:midpoint],item)
            else:
                return binarySearch(list[midpoint+1:],item)


list= [1,2,3,4,5,6,7,8,9,10,11,15]

print(binarySearch(list,5))

结果：

True