Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!thunder.mcrcim.mcgill.edu!snorkelwacker.mit.edu!mintaka!think.com!sdd.hp.com!spool2.mu.edu!uunet!mcsun!corton!irisa!raoult
From: raoult@irisa.fr (Jean-Claude Raoult)
Newsgroups: comp.theory
Subject: Re: lower-bound for binary search
Message-ID: <1991Jan30.101200.4395@irisa.fr>
Date: 30 Jan 91 10:12:00 GMT
References: <56531@eerie.acsu.Buffalo.EDU> <56707@eerie.acsu.Buffalo.EDU>
Sender: news@irisa.fr
Organization: IRISA, Rennes (Fr)
Lines: 8


   I am not so sure, that a lower bound for an algorithm searching in
a sorted list "by all means" can exist. If your means is divination, then
your search can be done in O(1). More seriously, it may happen that your
sorted list is at the same time a h-code table filled with a perfect
hashing function. Then again, you will get your answer in O(1).
   If the only thing you know is that your list is sorted, then you must
use only comparisons - hence the log(n) bound.