As in Lecture video of finding a name in telephone directory we get to half and choose one half where we can find the name. But my question is when the names are random how to effectively find a name. Like in a class of students all names are random then how to effectively find a name. (without sorting)


Sorting is one of the technique that is used in solving MANY problems(by MANY, I mean literally many), and that is why, one of the most prestigious book of computer science, The Art of Computer Programming devotes more than half of one of its book for sorting.

The power of sorting can be recognized by the fact that lookup in an unsorted list takes O(n) while on a sorted list reduces down to O(log2n) which is a fairly good performance. If you take input size to be around 107, then lookup in sorted array takes something around 24 comparisons while in unsorted array takes 107-1 comparisons, and hence proportional time. However, the words "without sorting" are like cutting the fingers of a programmer.

AFAIK, without sorting, one can use a data structure like hash table to store elements. The absence of a sorting algorithm may be compensated by the hash function. But still we would not get that efficiency because the complexity could be reduced to O(1+α) in case you have resolved collisions by chaining else O(1) if you took help of probing, where α was the ratio of total number of keys mapped to number of slots in hash table. In such a case, complexity still remains linear but just constant terms in that expression make the change and optimize the lookup process.

BTW another data structure can be used for such a purpose unless you broaden the definition of sorting and make clear about the constraint. This data structure works like quicksort. One could use Binary Search Tree, to store elements and then enjoy lookup in O(log2n) on a (assumed)balanced BST excluding power in pre-computing to create a BST out of input. Although BST in worst case can perform simply as an array taking O(n) time for lookup. But still when you say random, that benefits a BST.

By far, my best approach for such problem would be BST, although there exists something like Bloom Filters that can be used to test whether a key exists in a set of keys or not, but to be true, I know not much about them, so personally I would avoid attacking the problem with its help.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .