sti*_*ing 8 python algorithm binary-search data-structures python-3.x
我在leetcode上经历了这个问题的艰难时期。
我不得不查找解决方案，因为出于某种原因，我的代码总是会遇到一些问题。当在数组中查找不存在的目标编号时，我拥有的当前代码仍然无限循环。
我正在寻找一些帮助，以帮助您了解是否存在更直观的方法来解决此问题，并且还有助于修复我的代码。
我认为我不需要此行：
if nums[mid] == target or nums[low] == target or nums[high] == target:
return target
我想知道如何做才能确保如果我有一个由1-3个数字组成的数组，那么我的代码无需指定此条件语句就能找到目标。这是几个例子
print(search([1, 2, 3], 1))
print(search([1], 1))
print(search([2, 1], 1))
另外，在这样的例子中，print(search([5, 1, 2, 3, 4], 6))
我的代码永远不会返回-1
if nums[mid] == target or nums[low] == target or nums[high] == target:
return target
从遇到类似于我上面的解决方案的多个解决方案开始，人们都说是这样，O(logn)但是我不知道我们何时将其移动low并移动high1。这使我相信该解决方案是最坏的情况O(n)
寻求帮助！
这是一个略有不同的版本
def search(nums, target):
low = 0
high = len(nums)-1
while low <= high:
mid = (low + high) // 2
l = nums[low]
m = nums[mid]
h = nums[high]
if target == l:
return low
if target == m:
return mid
if target == h:
return high
if any([
l < m < h and target < m,
l == m < h and target > m,
l > m < h and target > l and target > m,
l > m < h and target < l and target < m,
l < m > h and target > l and target < m
]):
high = mid
elif any([
l < m < h and target > m,
l > m < h and target > m and target < h,
l < m > h,
]):
low = mid
elif target < l or target > h:
break
elif l == m == h:
break
else:
raise Exception("This is not possible, only if some values are reverse/unordered!")
return -1
使用此数据进行测试（第一列是目标，第二列是列表，第三列是结果索引）：
-10 [1] -1
1 [1] 0
22 [1] -1
-10 [1, 2] -1
1 [1, 2] 0
2 [1, 2] 1
22 [1, 2] -1
-10 [2, 1] -1
1 [2, 1] 1
2 [2, 1] 0
22 [2, 1] -1
-10 [1, 5] -1
1 [1, 5] 0
5 [1, 5] 1
22 [1, 5] -1
-10 [5, 1] -1
1 [5, 1] 1
5 [5, 1] 0
22 [5, 1] -1
-10 [1, 2, 3] -1
1 [1, 2, 3] 0
2 [1, 2, 3] 1
3 [1, 2, 3] 2
22 [1, 2, 3] -1
-10 [3, 1, 2] -1
1 [3, 1, 2] 1
2 [3, 1, 2] 2
3 [3, 1, 2] 0
22 [3, 1, 2] -1
-10 [2, 3, 1] -1
1 [2, 3, 1] 2
2 [2, 3, 1] 0
3 [2, 3, 1] 1
22 [2, 3, 1] -1
-10 [1, 5, 10] -1
1 [1, 5, 10] 0
5 [1, 5, 10] 1
2 [1, 5, 10] -1
10 [1, 5, 10] 2
22 [1, 5, 10] -1
-10 [10, 1, 5] -1
1 [10, 1, 5] 1
5 [10, 1, 5] 2
2 [1, 5, 10] -1
10 [10, 1, 5] 0
22 [10, 1, 5] -1
-10 [5, 10, 1] -1
1 [5, 10, 1] 2
5 [5, 10, 1] 0
2 [1, 5, 10] -1
10 [5, 10, 1] 1
22 [5, 10, 1] -1
-10 [1, 2, 3, 4] -1
1 [1, 2, 3, 4] 0
2 [1, 2, 3, 4] 1
3 [1, 2, 3, 4] 2
4 [1, 2, 3, 4] 3
-10 [1, 2, 3, 4] -1
-10 [4, 1, 2, 3] -1
1 [4, 1, 2, 3] 1
2 [4, 1, 2, 3] 2
3 [4, 1, 2, 3] 3
4 [4, 1, 2, 3] 0
-10 [4, 1, 2, 3] -1
-10 [3, 4, 1, 2] -1
1 [3, 4, 1, 2] 2
2 [3, 4, 1, 2] 3
3 [3, 4, 1, 2] 0
4 [3, 4, 1, 2] 1
-10 [3, 4, 1, 2] -1
-10 [2, 3, 4, 1] -1
1 [2, 3, 4, 1] 3
2 [2, 3, 4, 1] 0
3 [2, 3, 4, 1] 1
4 [2, 3, 4, 1] 2
-10 [2, 3, 4, 1] -1
-10 [1, 5, 8, 22] -1
1 [1, 5, 8, 22] 0
5 [1, 5, 8, 22] 1
8 [1, 5, 8, 22] 2
22 [1, 5, 8, 22] 3
10 [1, 5, 8, 22] -1
100 [1, 5, 8, 22] -1
-10 [22, 1, 5, 8] -1
1 [22, 1, 5, 8] 1
5 [22, 1, 5, 8] 2
8 [22, 1, 5, 8] 3
22 [22, 1, 5, 8] 0
10 [22, 1, 5, 8] -1
100 [22, 1, 5, 8] -1
-10 [8, 22, 1, 5] -1
1 [8, 22, 1, 5] 2
5 [8, 22, 1, 5] 3
8 [8, 22, 1, 5] 0
22 [8, 22, 1, 5] 1
10 [8, 22, 1, 5] -1
100 [8, 22, 1, 5] -1
-10 [5, 8, 22, 1] -1
1 [5, 8, 22, 1] 3
5 [5, 8, 22, 1] 0
8 [5, 8, 22, 1] 1
22 [5, 8, 22, 1] 2
10 [5, 8, 22, 1] -1
100 [5, 8, 22, 1] -1
5 [5, 1, 2, 3, 4] 0
1 [5, 1, 2, 3, 4] 1
2 [5, 1, 2, 3, 4] 2
3 [5, 1, 2, 3, 4] 3
4 [5, 1, 2, 3, 4] 4
5 [4, 5, 1, 2, 3] 1
1 [4, 5, 1, 2, 3] 2
2 [4, 5, 1, 2, 3] 3
3 [4, 5, 1, 2, 3] 4
4 [4, 5, 1, 2, 3] 0
5 [3, 4, 5, 1, 2] 2
1 [3, 4, 5, 1, 2] 3
2 [3, 4, 5, 1, 2] 4
3 [3, 4, 5, 1, 2] 0
4 [3, 4, 5, 1, 2] 1
5 [2, 3, 4, 5, 1] 3
1 [2, 3, 4, 5, 1] 4
2 [2, 3, 4, 5, 1] 0
3 [2, 3, 4, 5, 1] 1
4 [2, 3, 4, 5, 1] 2
5 [5, 77, 1, 2, 3] 0
77 [5, 77, 1, 2, 3] 1
1 [5, 77, 1, 2, 3] 2
2 [5, 77, 1, 2, 3] 3
3 [5, 77, 1, 2, 3] 4
5 [5, 6, 1, 2, 3] 0
6 [5, 6, 1, 2, 3] 1
1 [5, 6, 1, 2, 3] 2
2 [5, 6, 1, 2, 3] 3
3 [5, 6, 1, 2, 3] 4
5 [5, 6, 1, 2, 3, 4] 0
6 [5, 6, 1, 2, 3, 4] 1
1 [5, 6, 1, 2, 3, 4] 2
2 [5, 6, 1, 2, 3, 4] 3
3 [5, 6, 1, 2, 3, 4] 4
4 [5, 6, 1, 2, 3, 4] 5
之所以不是O(n)是因为在O(n)的情况下，这意味着算法的性能将随着数据的增加而线性下降，而在这种情况下，性能以对数方式下降输入数据的增加，对于每次迭代，我们将数据集拆分得越来越小。
| 归档时间： |
|
| 查看次数： |
222 次 |
| 最近记录： |