Binary search 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 is the most efficient way to do this?
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?
Thank!
source to share
Some suggestion:
1) First try to find the middle element (623 in the example) sorted short list
, the result will beindex
2) Divide the shortlist into bottom half (all items are smaller than the middle item) and the top half (all items are larger than the middle item).
3) For the bottom half, we start searching from 0
to a index
long list, and for the top half, we start searching from index + 1
to n
(n is the length of the long list)
4) Repeat step 1 for the two halves.
source to share
Your idea of keeping track of boundaries and narrowing down your search range is good. Your approach to finding records alternately from the left and right ends is as good as traversing a small array from left to right and just adjusting the lower bound. (Unless you know something about key distribution in S.)
I think you should work recursively on a small array and cut in half for each recursive binary search style. Search 623
in the array L
and find the index k
. Then go to the left subarray and find entries in {22, 255}
in L[0...k]
. Then go back to the right and find the entries {723, 876}
in L[k + 1...|L|]
.
source to share
Since you mentioned in one of the comments that your lists are huge, if your shorter list has a length comparable to that of a longer list, you can simply set two pointers at the beginning of both lists and move one at each step that points to the smaller element. on right. When both pointers point to equal values, you've found a match. It will be O(s + l)
, which will be faster than the naive O(s log l)
one if s
close to l
( s
- the length of the shorter list, l
- the length of the longer list).
source to share