Python中的二分查找
本帖最后由 陶远航 于 2023-4-29 10:47 编辑Python中的二分查找（纯Python实现）
注意输入时要用英文的逗号
记得评分{:10_256:}
源码：
from __future__ import annotations
import bisect
def bisect_left(
sorted_collection: list, 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 < item:
lo = mid + 1
else:
hi = mid
return lo
def bisect_right(
sorted_collection: list, 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 <= item:
lo = mid + 1
else:
hi = mid
return lo
def insort_left(
sorted_collection: list, 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, 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, item: int) -> int | None:
left = 0
right = len(sorted_collection) - 1
while left <= right:
midpoint = left + (right - left) // 2
current_item = sorted_collection
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, item: int) -> int | None:
index = bisect.bisect_left(sorted_collection, item)
if index != len(sorted_collection) and sorted_collection == item:
return index
return None
def binary_search_by_recursion(
sorted_collection: list, item: int, left: int, right: int
) -> int | None:
if right < left:
return None
midpoint = left + (right - left) // 2
if sorted_collection == item:
return midpoint
elif sorted_collection > 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} 中.")
你没评分吧{:10_256:}
赶紧的（还有44积分就到中级鱼油了，给个荣誉也行啊，或者评个鱼币回点血）
各种排序算法：https://fishc.com.cn/thread-227638-1-1.html 感谢评分 玉璧 顶 顶 重复发帖( sfqxx_小 发表于 2023-4-29 11:49
重复发帖(
已经删了 陶远航 发表于 2023-4-29 12:51
已经删了
{:10_275:} @不二如是 求支持 顶~ {:7_146:}币币~ 币币币币币币币币币币...... 元豪 发表于 2023-4-29 14:35
币币币币币币币币币币......
中奖绝缘体... 陶远航 发表于 2023-4-29 14:53
中奖绝缘体...
55555{:10_266:} 中{:10_269:} 陶远航 发表于 2023-4-29 13:37
@不二如是 求支持
加一些解释会更好 渔币 再来 {:10_323:} 6666