马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
x
本帖最后由 陶远航 于 2023-4-29 10:47 编辑
Python中的二分查找（纯Python实现）
注意输入时要用英文的逗号
记得评分
源码：from __future__ import annotations
import bisect
def bisect_left(
sorted_collection: list[int], item: int, lo: int = 0, hi: int = -1
) -> int:
if hi < 0:
hi = len(sorted_collection)
while lo < hi:
mid = lo + (hi - lo) // 2
if sorted_collection[mid] < item:
lo = mid + 1
else:
hi = mid
return lo
def bisect_right(
sorted_collection: list[int], item: int, lo: int = 0, hi: int = -1
) -> int:
if hi < 0:
hi = len(sorted_collection)
while lo < hi:
mid = lo + (hi - lo) // 2
if sorted_collection[mid] <= item:
lo = mid + 1
else:
hi = mid
return lo
def insort_left(
sorted_collection: list[int], item: int, lo: int = 0, hi: int = -1
) -> None:
sorted_collection.insert(bisect_left(sorted_collection, item, lo, hi), item)
def insort_right(
sorted_collection: list[int], item: int, lo: int = 0, hi: int = -1
) -> None:
sorted_collection.insert(bisect_right(sorted_collection, item, lo, hi), item)
def binary_search(sorted_collection: list[int], item: int) -> int | None:
left = 0
right = len(sorted_collection) - 1
while left <= right:
midpoint = left + (right - left) // 2
current_item = sorted_collection[midpoint]
if current_item == item:
return midpoint
elif item < current_item:
right = midpoint - 1
else:
left = midpoint + 1
return None
def binary_search_std_lib(sorted_collection: list[int], item: int) -> int | None:
index = bisect.bisect_left(sorted_collection, item)
if index != len(sorted_collection) and sorted_collection[index] == item:
return index
return None
def binary_search_by_recursion(
sorted_collection: list[int], item: int, left: int, right: int
) -> int | None:
if right < left:
return None
midpoint = left + (right - left) // 2
if sorted_collection[midpoint] == item:
return midpoint
elif sorted_collection[midpoint] > item:
return binary_search_by_recursion(sorted_collection, item, left, midpoint - 1)
else:
return binary_search_by_recursion(sorted_collection, item, midpoint + 1, right)
if __name__ == "__main__":
user_input = input("请用逗号分隔输入数字(从小到大):").strip()
#一定要用英文的逗号
collection = sorted(int(item) for item in user_input.split(","))
target = int(input("请输入要在列表中查找的单个数字:"))
result = binary_search(collection, target)
if result is None:
print(f"{target} 未在 {collection} 中找到.")
else:
print(f"{target} 被找到在 {result} 位置在 {collection} 中.")
赶紧的（还有44积分就到中级鱼油了，给个荣誉也行啊，或者评个鱼币回点血）
各种排序算法：https://fishc.com.cn/thread-227638-1-1.html | 
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2023-4-29 10:40:01
置顶卡
千斤顶
显身卡
楼主
发表于 2023-4-29 11:49:43
币币~
发表于 2023-4-29 15:18:48
