Check if list has a list of values

Question

I have been trying to figure out an efficient algorithm that can check if a list of values contains a list of values. Both lists are sorted in ascending order.

For example:

Check if

var listToSearch = [1,2,3,4,5,6,7]

contains

var searchValues = [1,2,3]

Without iterating through the list for each value in searchValues. Nor do I want to use something like binary search for each value in searchValues.

I tried creating a modified binary search for this but it does not work. Is there some modification of binary search but for multiple search values or any other algorithm designed for this problem?

Edit: I want to check if listToSearch has ANY of the values in searchValues (not the entire sublist). So, for example the algorithm could return [true, true, true] since 1,2, and 3 are all found in listToSearch

Answer 1

If you have a linked list, then you are going to need to iterate each elements in sequence. You can have a binary search if you use an array instead.

Let's call L the list you are searching, and V the list of values that are searched for.

Your search function should return the sublist of L that follows the element v from V that you are searching for. Since elements are sorted, you know that the next element in V is going to be greater than v, and thus you only need to search in the sublist that follows v in L.

For example, say your lists are named as follow:

L = [1,2,3,4,5,6,7]
V = [3,4,7,8]

1. Search for 3 in [1,2,3,4,5,6,7].
2. Search for 4 in [4,5,6,7]
3. Search for 7 in [5,6,7]
4. Search for 8 in []

Anytime your search returns an empty list, the result for the search element is false (true otherwise). Since you advance in both lists at the same time, you are avoiding some useless search.

Answer 2

Since both lists are sorted, you can do this with a slightly modified merge algorithm. You don't say what language you're using for, so I'll use a C-like psuedocode:

// ListToFind is the list of items to look for
// ListOfItems is the list of items to be searched
ixListToFind = 0   
isListOfItems = 0

while (ixListToFind < ListToFind.Count && ixListOfItems < ListOfItems.Count)
{
    if (ListToFind[ixListToFind] < ListOfItems[ixListOfItems])
    {
        // This item not found in the list. So move to the next one.
        ixListToFind = ixListToFind + 1
    }
    else if (ListToFind[ixListToFind] > ListOfItems[ixListOfItems])
    {
        // Move to the next item
        ixListOfItems = ixListOfItems + 1
    }
    else
    {
        // Found the item
        // Output or process it ... whatever.
        // Then move to the next item
        ixListToFind = ixListToFind + 1
    }
}

This works well if the number of items to find and the size of the list you're searching in are relatively similar in size. If you're looking for 5 items in a list of 20, for example, this will be great. But if you're looking for 100 items in a list of a million, then you'll probably want to use binary search. It depends on how many times you'll look for items in the same list.