查找数字python实现

Lihoon · 2020-3-20 18:24:35

马上注册,享受更多特权

您需要登录才可以下载或查看，没有帐号？立即注册

x

1、直接查找法

#-*- coding:utf-8 -*-
#Created Date: 2020/03/18
import random
import timeit
import sys
def random_list(n):
"""返回一个长度为n的整数列表"""
list = []
for num in range(n):
list.append(random.randrange(1000))
return list
def quick_sort(list):
"""采用快速排序法对生成的随机数组进行排序"""
if len(list) <= 1:
return list
left = []
right = []
for idx in list[1:]:
if idx <= list[0]:
left.append(idx)
else:
right.append(idx)
return quick_sort(left) + [list[0]] + quick_sort(right)
def sequential_search(list, key):
# print("list = {}".format(list))
# print("Find the number: %d" % key)
for i in range(len(list)):
if list[i] == key:
return i
return -1
# 输入自定义数组长度
len_list = input("\nPlease input the length of list: ")
# 调用random_list()函数生成随机数组
source_list = random_list(int(len_list))
print("source_list:{}".format(source_list))
# 调用quick_sort()函数排序数组
sort_list = quick_sort(source_list)
print("sorted list: {}".format(sort_list))
# 手动输入关键词，调用sequential_search()函数搜索
key = int(input("key: "))
result = sequential_search(sort_list, key)
if result >= 0:
print("\n{} is in the list, and the index is: {}".format(key, result))
else:
print("\n{} is not in the list.".format(key))

复制代码

2、二分查找法

#-*- coding:utf-8 -*-
#Created Date: 2020/03/18
import random
import timeit
import sys
def random_list(n):
"""返回一个长度为n的整数列表"""
list = []
for num in range(n):
list.append(random.randrange(1000))
return list
def quick_sort(list):
"""采用快速排序法对生成的随机数组进行排序"""
if len(list) <= 1:
return list
left = []
right = []
for idx in list[1:]:
if idx <= list[0]:
left.append(idx)
else:
right.append(idx)
return quick_sort(left) + [list[0]] + quick_sort(right)
def binary_search(list, key):
list_len = len(list)
left = 0
right = list_len - 1
while right - left > 1:
mid = (left + right) // 2
if key < list[mid]:
right = mid
print("finding...")
elif key > list[mid]:
left = mid
print("finding...")
else:
print("finded")
return mid
if key == list[left]:
print("finded")
return left
elif key == list[right]:
print("finded")
return right
else:
print("not find")
return -1
# 输入自定义数组长度
len_list = input("\nPlease input the length of list: ")
# 调用random_list()函数生成随机数组
source_list = random_list(int(len_list))
print("source_list:{}".format(source_list))
# 调用quick_sort()函数排序数组
sort_list = quick_sort(source_list)
print("sorted list: {}".format(sort_list))
# 手动输入关键词，调用binary_search()函数搜索
key = int(input("key: "))
result = binary_search(sort_list, key)
if result >= 0:
print("\n{} is in the list, and the index is: {}".format(key, result))
else:
print("\n{} is not in the list.".format(key))

复制代码

3、斐波那契查找法

#-*- coding:utf-8 -*-
#Created Date: 2020/03/19
import random
import sys
def random_list(num):
"""生成随机数组"""
list = []
for i in range(num):
list.append(random.randrange(999))
return list
def quick_sort(list):
"""排序"""
if len(list) <= 1:
return list
left = []
right = []
for i in list[1:]:
if i <= list[0]:
left.append(i)
else:
right.append(i)
return quick_sort(left) + [list[0]] + quick_sort(right)
def fibonacci(n):
"""定义斐波那契数列，并输出数列的最后一个值"""
fib_list = [1, 1]
while n > 1:
fib_list.append(fib_list[-1] + fib_list[-2])
n -= 1
return fib_list[-1]
def fibonacci_search(list, key):
"""斐波那契数列搜索"""
len_list = len(list)
left = 0
right = len_list - 1
range_list = len_list - 1
k = 1
while fibonacci(k) -1 < range_list:
k += 1
while range_list > 1:
print("k = %d" % k)
mid = left + fibonacci(k -1)
if key < list[mid]:
right = mid - 1
k = 1
range_list = right - left
elif key == list[mid]:
return mid
else:
left = mid + 1
k = 1
range_list = right - left
if key == list[left]:
return left
elif key == list[right]:
return right
else:
return -1
num = input("请输出随机数列的长度：")
source_list = random_list(int(num))
print("生成的随机数组为：{}".format(source_list))
sorted_list = quick_sort(source_list)
print("排序后的数组为：{}".format(sorted_list))
key = int(input("\n请输入搜索的关键词："))
result = fibonacci_search(sorted_list, key)
if result >= 0:
print("{}在这个数列中，它的下标是：{}.".format(key, result))
else:
print("{}不在这个数列中.".format(key))

复制代码

zhu · 2020-3-28 15:58:54

给楼主点赞

帐号		自动登录	找回密码
密码			立即注册

[资料分享] 查找数字python实现

马上注册,享受更多特权

已有 0 人打赏作者

楼主其他主题

热点推荐

底部导航

积分管理

资料下载

有技术问题，就上汇川技术社区