我已经制定了一个二进制搜索算法biSearch（A，high，low，key）。它接受一个已排序的数组和一个键，并吐出键在数组中的位置。高和低是搜索范围的最小值和最大值。
几乎可以解决，除了一个问题：
[在第二个“迭代”上（不确定递归等效项是什么），条件得到满足，算法应停止运行并返回“索引”。我评论了这种情况。相反，最终发生的是即使前面的条件为true，代码也继续到下一个条件。正确的结果5被覆盖，新的结果是一个无类型对象。在我的代码中，我在大写处注释了问题发生的位置。非常感谢您的帮助，在此先感谢您！
"""
Created on Sat Dec 28 18:40:06 2019
"""
def biSearch(A, key, low = False, high = False):
if low == False:
low = 0
if high == False:
high = len(A)-1
if high == low:
return A[low]
mid = low + int((high -low)/ 2)
# if key == A[mid] : two cases
if key == A[mid] and high - low == 0: #case 1: key is in the last pos. SHOULD STOP RUNNING HERE
index = mid
return index
elif key == A[mid] and (high - low) > 0:
if A[mid] == A[mid + 1] and A[mid]==A[mid -1]: #case 2: key isnt last and might be repeated
i = mid -1
while A[i] == A[i+1]:
i +=1
index = list(range(mid- 1, i+1))
elif A[mid] == A[mid + 1]:
i = mid
while A[i]== A[i+1]:
i += 1
index = list(range(mid, i+1))
elif A[mid] == A[mid -1]:
i = mid -1
while A[i] == A[i +1]:
i += 1
index = list(range(mid, i +1))
elif key > A[mid] and high - low > 0: # BUT CODE EXECTUES THIS LINE EVEN THOUGH PRECEDING IS ALREADY MET
index = biSearch(A, key, mid+1, high)
elif key < A[mid] and high - low > 0:
index = biSearch(A, key, low, mid -1)
return index
elif A[mid] != key: # if key DNE in A
return -1
#biSearch([1,3,5, 4, 7, 7,7,9], 1, 8, 7)
#x = biSearch([1,3,5, 4, 7,9], 1, 6, 9)
x = biSearch([1,3,5, 4, 7,9],9)
print(x)
# x = search([1,3,5, 4, 7,9], 9)
此功能不是二进制搜索。二进制搜索的时间复杂度应为O（log（n））并适用于预排序列表，但是此算法的复杂度至少为O（n log（n）），因为它会为每个递归调用对输入参数列表进行排序。即使不进行排序，每个调用也会有类似list(range(mid, i +1))的线性语句，从而使复杂度呈二次方。使用list#index进行线性搜索会更好。
该函数更改了其输入参数，这是任何搜索功能都不应该做的（我们要搜索，而不是搜索and排序）。
除了效率和变异性之外，逻辑很难解析，在任何情况下都过分杀伤力。并非所有嵌套的条件条件都导致list#index，因此默认情况下可能会产生return。
您可以使用内置的return None模块：
bisect[如果您必须作为练习来手工编写，请先查看bisect的>>> from bisect import *
>>> bisect_left([1,2,2,2,2,3,4,4,4,4,5], 2)
1
>>> bisect_left([1,2,2,2,2,3,4,4,4,4,5], 4)
6
>>> bisect_right([1,2,2,2,2,3,4,4,4,4,5], 4)
10
>>> bisect_right([1,2,2,2,2,3,4,4,4,4,5], 2)
5
>>> bisect_right([1,2,2,2,2,3,4,4,4,4,5], 15)
11
>>> bisect_right([1,2,5,6], 3)
2
：
bisect_left这很容易递归实现（如果需要），然后根据内置函数进行测试：
source code
逻辑上，对于任何呼叫框，只有3种可能性：
def bisect_left(a, x, lo=0, hi=None):
"""Return the index where to insert item x in list a, assuming a is sorted.
The return value i is such that all e in a[:i] have e < x, and all e in
a[i:] have e >= x. So if x already appears in the list, a.insert(x) will
insert just before the leftmost x already there.
Optional args lo (default 0) and hi (default len(a)) bound the
slice of a to be searched.
"""
if lo < 0:
raise ValueError('lo must be non-negative')
if hi is None:
hi = len(a)
while lo < hi:
mid = (lo+hi)//2
# Use __lt__ to match the logic in list.sort() and in heapq
if a[mid] < x: lo = mid+1
else: hi = mid
和def bisect_left(a, target, lo=0, hi=None):
if hi is None: hi = len(a)
mid = (hi + lo) // 2
if lo >= hi:
return mid
elif a[mid] < target:
return bisect_left(a, target, mid + 1, hi)
return bisect_left(a, target, lo, mid)
if __name__ == "__main__":
from bisect import bisect_left as builtin_bisect_left
from random import choice, randint
from sys import exit
for _ in range(10000):
a = sorted(randint(0, 100) for _ in range(100))
if any(bisect_left(a, x) != builtin_bisect_left(a, x) for x in range(-1, 101)):
print("fail")
exit(1)
指针已交叉，在这种情况下，我们要么找到了元素，要么弄清楚了如果它在列表中应该在哪里；无论哪种方式，都返回中点。Python不会溢出整数，因此您可以使用简化的中点测试。