How do I efficiently search for a specific sequence in an array?

Question

I'm looking through large arrays for particular sequences and I feel like I'm approaching the problem using brute force rather than computer science.

Currently I'm looking sequentially down the large array for the first item in the search sequence, then checking each item after that until a failure or a complete match. This provides 100% accuracy but it's not very fast with large arrays.

I was never a computer science student so I missed out on many algorithm classes that plenty of people around here probably had. Is there a better way to search for sequences in arrays? I'm not necessarily interested in perfect accuracy if it makes a difference.

Answer 1

If you need to search for many patterns in the same sequence you can use suffix arrays

If you have to search for one pattern then you can improve a little over brute force with Boyer-Moore or Knuth-Morris-Pratt

Answer 2

There is no better way to search the array itself for candidates for matches. If you have no order you cannot discard candidates as a match or not without considering them.

That being said you can optimize candidate acceptance or rejection utilizing the method suggested by Janne.

Answer 3

How about using the Boyer-Moore algorithm? It's fairly simple and straightforward, and can increase the practical speed quite a lot, especially if your target sequence is fairly long. It's meant for searching for strings, but that's just a particular type of array of course.