#python #python-3.x #algorithm #data-structures #binary-search
#python #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
def search(nums, target):
low = 0
high = len(nums)-1
while low <= high:
mid = (low high) // 2
if nums[mid] == target or nums[low] == target or nums[high] == target:
return target
if nums[mid] <= nums[high]:
if target > nums[mid] and target <= nums[high]:
low = mid 1
else:
high = mid - 1
elif nums[mid] > nums[low]:
if target >= nums[low] and target < nums[mid]:
high = mid - 1
else:
low = mid 1
return -1
print(search([1, 2, 3], 1))
print(search([5, 4, 1, 2, 3], 2))
print(search([3, 4, 5, 1, 2], 2))
print(search([1], 1))
print(search([2, 1], 1))
print(search([5, 1, 2, 3, 4], 6))
Сталкиваясь с несколькими решениями, похожими на то, которое у меня есть выше, люди говорят, что это так, O(logn) но я не понимаю, как, когда мы перемещаем наше low и high на 1. Это заставляет меня поверить, что решение является наихудшим вариантом O(n)
Нужна помощь!
Комментарии:
1. Ну, одна проблема, которую я вижу, заключается в том, что вы делаете
return target, когда вы должны возвращать индекс цели.2. Вы не перемещаетесь
lowиhighна 1. Вы перемещаете его на 1 пункт от середины (поскольку вы уже проверили, чтоmiddleон не содержит правильного значения). Таким образом, на каждом шаге вы сокращаете половину пространства поиска, делая егоO(log n).
Ответ №1:
Вот немного другая версия
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) это означало бы, что производительность алгоритма будет линейно уменьшаться с увеличением объема данных, в то время как в этом случае производительность уменьшается логарифмическим образом с увеличением объема входных данных, поскольку для каждой итерации мы разбиваем набор данных на все меньшие и меньшие.
Комментарии:
1. Будет ли это «линейно увеличиваться с увеличением объема данных» и «логарифмически увеличиваться с увеличением объема входных данных»? Вместо «уменьшаться»?
2. @user9476376 нет, производительность всегда снижается с увеличением объема данных. Представьте, что вы обрабатываете 10 чисел вместо обработки 1000000000000000 чисел. Я пытаюсь выполнить измерение алгоритма с помощью
timeмодуля, но, похоже, мне нужно достаточное количество данных, чтобы отобразить что-то порядка секунд. Я несколько раз разбивал свой компьютер, делая это.3. печать (поиск([5,6, 1, 2, 3, 4], 6)) возвращает -1 с вашим кодом. @andreihondrari он должен возвращать 1
4. Спасибо всем за вашу помощь в решении этой проблемы!
5. @user9476376 Я начал с изложения на бумаге различных потенциальных вариантов, которые могут появиться в списке, например: только один элемент, два элемента, три элемента (в данном случае ясно, какой из них низкий, средний и высокий), а затем более 3 элементов. После этого я поворачивал все обращения, пока не получил для них все комбинации. После этого я начал создавать условия, которым соответствовал бы low / mid / high, если бы список находился в определенном состоянии, и я построил условия в коде на основе этого, указав, когда прерывать или изменять low / mid / high.
Ответ №2:
Ниже приведен исправленный код. Я прогнал его через leetcode, и он прошел.
Время выполнения: 52 мс, быстрее, чем 11,16% онлайн-заявок на Python для поиска в повернутом отсортированном массиве. Использование памяти: 11,9 МБ, менее 5,44% онлайн-заявок на Python для поиска в повернутом отсортированном массиве.
Это O(log n) потому, что мы уменьшаем размер нашей задачи наполовину на каждой итерации. Мы выбирали либо правую половину массива, либо левую половину массива при перемещении нашего максимума / минимума на каждой итерации.
Таким образом, размер вашего массива уменьшается следующим образом; n, n/2, n/4, ..., 1 и для перехода от log n к n требуется 1 несколько шагов, каждый раз уменьшая его вдвое.
class Solution(object):
def search(self, nums, target):
low = 0
high = len(nums)-1
while low <= high:
mid = (low high) // 2
print(low,high,mid)
if nums[mid] == target:
return mid
elif high==low:
return -1
elif nums[mid] <= nums[low] and nums[mid] <= nums[high] and nums[mid-1] >= nums[mid]:#mid is pivot
if target <= nums[high]:
low = mid 1
else:
high = mid - 1
elif nums[mid] > nums[mid-1] and nums[high] > nums[mid]: #pivot to left of mid
if nums[mid] > nums[low]: #pivot at start index
if target < nums[mid]:
high = mid - 1
else:
low = mid 1
else:
if target > nums[mid] and target <= nums[high]:
low = mid 1
elif target < nums[mid] or target >= nums[low]:
high = mid - 1
else:
return -1
elif nums[mid] >= nums[low] and nums[high] <= nums[mid]: #pivot to right of mid
if target <= nums[high] or target > nums[mid] :
low = mid 1
else:
high = mid - 1
else:
return -1
return -1