0

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

10
  • If the list you are searching doesn't have duplicates or you don't care about duplicates, you could use hashing to achieve what you are looking for.
    – burgermenu
    Apr 4, 2016 at 17:42
  • The lists wont have duplicates. Could you explain a little better? Thanks :)
    – boidkan
    Apr 4, 2016 at 17:48
  • 2
    What do you mean the binary search does not work ? Let j be the leftmost index where you start the binary search (initially 0). You binary search for the first element and if you find it you update j and then binary search for the second element starting at index j + 1 and so on. Apr 4, 2016 at 17:51
  • 2
    Could you clarify whether "contains a list of values" means that the list must contain all of the search values or that the list must contain a sublist that matches the search values?
    – Blrfl
    Apr 4, 2016 at 18:14

2 Answers 2

0

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.

0

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.

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.