Re: What search algorithm does in_array() use?

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. Cheers, Rob. -- .------------------------------------------------------------. | InterJinn Application Framework - http://www.interjinn.com | :------------------------------------------------------------: | An application and templating framework for PHP. Boasting | | a powerful, scalable system for accessing system services | | such as forms, properties, sessions, and caches. InterJinn | | also provides an extremely flexible architecture for | | creating re-usable components quickly and easily. | `------------------------------------------------------------'