Data Structures and Algorithms

   

Log N Algorithm for Search from Unstructured List

Authors: Dhananjay P. Mehendale

The unstructured search problem asks for search of some predefined number, called target, from given unstructured list of numbers. In this paper we propose a novel classical algorithm with complexity ~O(Log N) for searching the target from unstructured list of numbers. We propose a new algorithm, which achieves improvement of exponential order over existing algorithms. Suppose N is the largest number in the list then we consider N dimensional vector space with Euclidean basis. With each of the numbers in the given unstructured list we associate the unique basis vector among the vectors that form together the Euclidean basis. For example suppose j is a number in the list then we associate with this number j the unique basis vector in the above mentioned N-dimensional vector space, namely, |j> = transpose(0, 0, 0, … , 0, 0, 1, 0, 0, … , 0, 0, 0), where the there is entry 1 only at j-th place and every where else there is entry 0. We then divide the given list of numbers in two roughly equal parts (i.e. we divide the given bag containing scrambled numbers in two roughly equal parts and put them in two separate bags, Bag 1 and Bag 2). We represent the list of numbers in Bag 1, Bag 2 in the form of equally weighted superposition of basis vectors associated with the numbers contained in these bags, namely, we represent list in Bag 1 (Bag 2) as a single state formed by equally weighted superposition using orthonormal states forming Euclidean basis corresponding to numbers in the bag B1 (bag B2), namely, |Psi-1> (|Psi-2>). Let t be the target number. It will be represented as |t>. We then find the value of scalar product of target state |t> with |Psi-1> (or Psi-2>). It will revel us whether t belongs to Bag 1 (or Bag 2) which essentially enables us to carry out the binary search and to achieve above mentioned ~O(Log N) complexity!Also, representing list as superposition provides sorting of numbers instantly! One needs to read vector from left to right and prepare the desired sorted list!

Comments: 4 pages. Sorting algorithm is added.

Download: PDF

Submission history

[v1] 2013-06-22 15:24:38
[v2] 2013-06-28 01:21:51

Unique-IP document downloads: 1258 times

Vixra.org is a pre-print repository rather than a journal. Articles hosted may not yet have been verified by peer-review and should be treated as preliminary. In particular, anything that appears to include financial or legal advice or proposed medical treatments should be treated with due caution. Vixra.org will not be responsible for any consequences of actions that result from any form of use of any documents on this website.

Add your own feedback and questions here:
You are equally welcome to be positive or negative about any paper but please be polite. If you are being critical you must mention at least one specific error, otherwise your comment will be deleted as unhelpful.

comments powered by Disqus