как работает searchsort в python?

Чтобы прояснить мой вопрос, скажите, есть ли у меня массив a как Out[123]: [1, 3, 4, 6, 9, 10, 54] Когда я пытаюсь найти числа в списке, searchsort возвращает правильное значение, но когда Пробую что-то не из списка, возвращает абсурдное значение

вот некоторые результаты

In [131]: a
Out[131]: [1, 3, 4, 6, 9, 10, 54]

In [132]: searchsorted(a,1)
Out[132]: 0

In [133]: searchsorted(a,6)
Out[133]: 3

In [134]: searchsorted(a,[9,54,1])
Out[134]: array([4, 6, 0])

In [135]: searchsorted(a,[9,54,1,0])
Out[135]: array([4, 6, 0, 0])
***> # here 0 is not in the list, but turns up @ position 0***

In [136]: searchsorted(a,740)
Out[136]: 7
***> # here 0 is not in the list, but turns up @ position 7***

почему это происходит?


python search sortedlist
person Ars3nous    schedule 15.03.2013    source источник
comment
Что такое searchsorted?   -  person Volatility    schedule 15.03.2013
comment
searchsorted явно не является встроенным.   -  person thkang    schedule 15.03.2013
comment
@Volatility searchsorted — это функция numpy/scipy. docs.scipy.org/doc/numpy/reference/generated/   -  person Snakes and Coffee    schedule 15.03.2013

Ответы (3)


arrow_upward
11
arrow_downward

searchsorted сообщает вам, где находится элемент для гарантированного порядка:

Найдите индексы в отсортированном массиве a так, чтобы, если бы соответствующие элементы в v были вставлены перед индексами, порядок a был бы сохранен.

вставка 740 в позицию 7 сохранит порядок, как и вставка 0 в позицию 0.

person John Lyon    schedule 15.03.2013
comment
Если вы хотите определить, находится ли число в массиве, вы можете использовать == и nonzero для этого: len((a == 740)[0]) равно нулю. - person John Lyon; 15.03.2013
comment
Спасибо, @jozzas понял. Я думал, что он выполняет бинарный поиск. - person Ars3nous; 15.03.2013
comment
Или вы можете сделать 740==a[searchsorted(a, 740)], чтобы по-прежнему использовать бинарный поиск. - person goryh; 25.06.2019

arrow_upward
3
arrow_downward

searchsorted не говорит вам, где что находится, а говорит вам, куда что должно идти, чтобы список оставался упорядоченным.

Таким образом, 0 нужно будет вставить в позицию 0 перед 1. Точно так же 740 необходимо вставить в позицию 7 за текущим концом списка.

Вы можете убедиться в этом, прочитав документы здесь:

numpy.searchsorted(a, v, side='left', sorter=None)

Найдите индексы, в которые следует вставить элементы для поддержания порядка.

Найдите индексы в отсортированном массиве а так, что если бы соответствующие элементы в v были вставлены перед индексами, порядок a был бы сохранен.

person paxdiablo    schedule 15.03.2013
comment
Он также может сказать вам, где находятся вещи, которые находятся в индексе, если искомое значение находится в индексе 'left'. Использование бинарного поиска для определения локализации по-прежнему остается самым быстрым методом. - person Martijn Pieters; 19.04.2018

arrow_upward
1
arrow_downward

из документов указано, что он использует бинарный поиск для определения точки вставки элемента в отсортированном списке.

слово «точка вставки» означает, что если элемент I вставляется в индекс точки вставки N в отсортированном массиве A, массив A останется отсортированным с новым элементом I.

ваши примеры, такие как [9, 54, 1], бессмысленны, поскольку массив не отсортирован.

вы можете использовать модуль bisect в python, чтобы делать то же самое, без numpy.

person thkang    schedule 15.03.2013
comment
[9,54,1] - это не список для поиска, это список элементов для возврата точек вставки в a для. Он работает нормально, посмотрите результат. - person paxdiablo; 15.03.2013
comment
@paxdiablo да, я этого не видел - person thkang; 15.03.2013