1

I have a main numpy array a and I have another numpy array b. What I want to do is go through each element of b and check if that element exists in a. Keep in mind that both a and b are pretty massive, so I would like to avoid O(N) search times.

I know np.searchsorted(a,b) exists, but this provides an index at which I need to place b. This does not tell me if an element of b is present in a right off the bat.

My question is, is there a binary search algorithm built into numpy that simply reports True or False if an element from b exists in a? I am aware that I can write one but if there is a vectorized that is readily available, I could save some time.

Any advice would be appreciated!

Improve this question
1
  • 1
    Check the values in a at the indices returned and compare with the values in b. For each value in b, if value == a[i], then the value exists in a, otherwise it does not. If the input is large, the benefit of vectorization probably outweighs the penalty for the O(1) lookups. Commented Nov 12, 2022 at 22:12

1 Answer 1

Reset to default
2

Once you have completed the sorted search you can check if the elements at those indices are equal to the elements in b:

a = numpy.array([1,2,3,4,7])
b = numpy.array([1,4,5,7])
x = numpy.searchsorted(a,b)
boolean_array = a[x] == b

searchsorted indicates that with the default side = 'left' it ensures : a[i-1] < v <= a[i] so if a[i] is equal to the corresponding element in b then it gives the match you want.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Thank you for your answer @TadhgMcDonald-Jensen! Quick edge case, what do I do if an element of b is larger than max(a)? I expect to get an out-of-bounds error
My hack around this was that I changed your final line: boolean_array = np.hstack((a[x], False)) == b knowing that False is never going to be part of b
hmm... in that case you might be able to get away with just something like x[x>=a.size] = a.size-1 to truncate the indices, because you are then checking if the elements in a are equal to the elements in b it shouldn't break any logic

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.