Re: What search algorithm does in_array() use?

On Mon, January 29, 2007 7:03 pm, Robert Cummings wrote: > On Mon, 2007-01-29 at 17:12 -0600, Richard Lynch wrote: >> On Mon, January 29, 2007 11:20 am, Ken Dozier wrote: >> > Does in_array() use a search algorithm (i.e., binary search), or >> does >> > it >> > check sequentially each element in the array? >> >> Since there is no guarantee that the elements are in any particular >> order, it almost has to be sequential... > > There's no guarantee that the keys are in any particular order either > though... but the keys do receive special treatment :) > >> Ideal #2: >> Put the values in as keys, and use http://php.net/isset >> This will "hash" the values and have an O(1) lookup, I think. > > Only perfect hashes have O(1) lookup, and in practice there are very > few > perfect hashes set up in reality since the cost to produce a perfect > hash outweighs the time necessary to find the value. You'll find that > most lookup systems are on the order of O( lg n ). PHP is no > exception. I rememberd that after I hit "Send" Oh well. It's still way the hell better than what we suspect in_array() does. -- Some people have a "gift" link here. Know what I want? I want you to buy a CD from some starving artist. http://cdbaby.com/browse/from/lynch Yeah, I get a buck. So?