CODEWITHSUNDEEP
algorithmbinary-search
user2961927
user2961927

Reputation: 1728

Binary search for sorted multiple items

Suppose I have a long sorted list L={1, 2,.., 999, 1000} and a short sorted list S={22, 255, 623, 732, 876}.

In L, I want to search for every element of S. What's most efficient way to do it?

So far the method I came up with is:

1. Binary search for 22. Record the lower bound=23
2. Binary search for 876. Record the upper bound=875
3. Binary search for 255 in the range [lower bound=23, upper bound=875].
4. Set lower bound=256, and go on..

Is this the most efficient way? Is there any other way that can converge faster than this method?

Thanks!

Upvotes: 6

Views: 1967

Answers (3)

Ishamael
Ishamael

Reputation: 12795

Since you mentioned in one of the comments that your lists are huge, if your shorter list has length comparable to the lenght of the longer list, you can just set two pointers at the beginning of both lists, and at each step move one that points to the smaller element to the right. Whenever both pointers point at equal values, you found a match. This will be O(s + l), which will be faster than naive O(s log l) if s is close to l (s is the length of the shorter list, l is the length of the longer list).

Upvotes: 1

Pham Trung
Pham Trung

Reputation: 11294

Some suggestion:

1) First, try to find the middle element (623 in the example) of the sorted short list, the result is index

2) Divide the short list into lower half (which are all elements less than middle element) and upper half (which are all elements greater than middle element).

3) For lower half, we start to search from 0 to index of the long list, and for upper half, we start to search from index + 1 to n (n is length of long list)

4) Do step 1 recursively for the two halves.

Upvotes: 1

M Oehm
M Oehm

Reputation: 29136

Your idea to keep track of the bounds and to reduce the search range is good. Your approach of looking up entries alternately from the left and right end is as good as moving through the small array from left to right and just adjusting the lower bound. (Unless you know something on the distribution of the keys in S.)

I think you should work recursively on the small array and cut in in half on every recursion, binary-search style. Look up 623 in array L and find index k. Next recurse to the left subarray and look up the entries in {22, 255} in L[0...k]. Then recurse to the right and look up entries {723, 876} in L[k + 1...|L|].

Upvotes: 1

Related Questions