A fast natural algorithm for searching

In this note we present two natural algorithms—one for sorting, and another for searching a sorted list of items. Both algorithms work in O( N ) time, N being the size of the list. A combination of these algorithms can search an unsorted list in O( N ) time, an impossibility for classical algorithms. The same complexity is achieved by Grover's quantum search algorithm; in contrast to Grover's algorithm which is probabilistic, our method is guaranteed correct. Two applications will conclude this note.

Authors

• Joshua J. Arulanandham
• Cristian S. Calude
• Michael J. Dinneen

Keywords

• Searching
• Natural algorithms
• Data structures