Python中的二分查找

陶远航

Python中的二分查找（纯Python实现）
注意输入时要用英文的逗号
记得评分
源码：

1. from __future__ import annotations
   
2. import bisect
   
3. 
   
4. def bisect_left(
   
5.     sorted_collection: list[int], item: int, lo: int = 0, hi: int = -1
   
6. ) -> int:
   
7.     if hi < 0:
   
8.         hi = len(sorted_collection)
   
9. 
   
10.     while lo < hi:
    
11.         mid = lo + (hi - lo) // 2
    
12.         if sorted_collection[mid] < item:
    
13.             lo = mid + 1
    
14.         else:
    
15.             hi = mid
    
16. 
    
17.     return lo
    
18. 
    
19. 
    
20. def bisect_right(
    
21.     sorted_collection: list[int], item: int, lo: int = 0, hi: int = -1
    
22. ) -> int:
    
23.     if hi < 0:
    
24.         hi = len(sorted_collection)
    
25. 
    
26.     while lo < hi:
    
27.         mid = lo + (hi - lo) // 2
    
28.         if sorted_collection[mid] <= item:
    
29.             lo = mid + 1
    
30.         else:
    
31.             hi = mid
    
32. 
    
33.     return lo
    
34. 
    
35. 
    
36. def insort_left(
    
37.     sorted_collection: list[int], item: int, lo: int = 0, hi: int = -1
    
38. ) -> None:
    
39.     sorted_collection.insert(bisect_left(sorted_collection, item, lo, hi), item)
    
40. 
    
41. 
    
42. def insort_right(
    
43.     sorted_collection: list[int], item: int, lo: int = 0, hi: int = -1
    
44. ) -> None:
    
45.     sorted_collection.insert(bisect_right(sorted_collection, item, lo, hi), item)
    
46. 
    
47. 
    
48. def binary_search(sorted_collection: list[int], item: int) -> int | None:
    
49.     left = 0
    
50.     right = len(sorted_collection) - 1
    
51. 
    
52.     while left <= right:
    
53.         midpoint = left + (right - left) // 2
    
54.         current_item = sorted_collection[midpoint]
    
55.         if current_item == item:
    
56.             return midpoint
    
57.         elif item < current_item:
    
58.             right = midpoint - 1
    
59.         else:
    
60.             left = midpoint + 1
    
61.     return None
    
62. 
    
63. 
    
64. def binary_search_std_lib(sorted_collection: list[int], item: int) -> int | None:
    
65.     index = bisect.bisect_left(sorted_collection, item)
    
66.     if index != len(sorted_collection) and sorted_collection[index] == item:
    
67.         return index
    
68.     return None
    
69. 
    
70. 
    
71. def binary_search_by_recursion(
    
72.     sorted_collection: list[int], item: int, left: int, right: int
    
73. ) -> int | None:
    
74.     if right < left:
    
75.         return None
    
76. 
    
77.     midpoint = left + (right - left) // 2
    
78. 
    
79.     if sorted_collection[midpoint] == item:
    
80.         return midpoint
    
81.     elif sorted_collection[midpoint] > item:
    
82.         return binary_search_by_recursion(sorted_collection, item, left, midpoint - 1)
    
83.     else:
    
84.         return binary_search_by_recursion(sorted_collection, item, midpoint + 1, right)
    
85. 
    
86. 
    
87. if __name__ == "__main__":
    
88.     user_input = input("请用逗号分隔输入数字(从小到大):").strip()
    
89.     #一定要用英文的逗号
    
90.     collection = sorted(int(item) for item in user_input.split(","))
    
91.     target = int(input("请输入要在列表中查找的单个数字:"))
    
92.     result = binary_search(collection, target)
    
93.     if result is None:
    
94.         print(f"{target} 未在 {collection} 中找到.")
    
95.     else:
    
96.         print(f"{target} 被找到在 {result} 位置在 {collection} 中.")

复制代码

你没评分吧
赶紧的（还有44积分就到中级鱼油了，给个荣誉也行啊，或者评个鱼币回点血）
各种排序算法：https://fishc.com.cn/thread-227638-1-1.html

陶远航

感谢评分

歌者文明清理员

玉璧

陶远航

顶

sfqxx

顶

sfqxx_小

重复发帖(

陶远航

sfqxx_小 发表于 2023-4-29 11:49
重复发帖(

已经删了

sfqxx

陶远航 发表于 2023-4-29 12:51
已经删了

陶远航

@不二如是 求支持

元豪

顶~

元豪

币币~

元豪

币币币币币币币币币币......

陶远航

元豪 发表于 2023-4-29 14:35
币币币币币币币币币币......

中奖绝缘体...

元豪

陶远航 发表于 2023-4-29 14:53
中奖绝缘体...

55555

元豪

中

不二如是

陶远航 发表于 2023-4-29 13:37
@不二如是 求支持

加一些解释会更好

平凡之路1314

渔币

平凡之路1314

再来

desc

long90

6666