php.net |  support |  documentation |  report a bug |  advanced search |  search howto |  statistics |  random bug |  login

go to bug id or search bugs for

Request #59454 apc_binary_search() binary search for key in an array
Submitted: 2010-10-09 14:52 UTC Modified: 2010-10-09 16:10 UTC
From: joaoptm78 at gmail dot com Assigned:
Status: Wont fix Package: APC (PECL)
PHP Version: Irrelevant OS:
Private report: No CVE-ID: None
View Developer Edit
 [2010-10-09 14:52 UTC] joaoptm78 at gmail dot com 
Description:
------------
Would be nice to have a function to binary search for a value on a stored array (sorted) returning its first match, similar to the function INTERVAL() in mysql.

http://dev.mysql.com/doc/refman/4.1/en/comparison-operators.html#function_interval

For example if I have this array(0, 5, 15, 20) and I'm searching for 10 I would like to get 15 as the result.

It's possible to do this with first apc_fetch then search the array on my own but would like a faster and more efficient way to do it because the array could be quite large.

Patches

Pull Requests

History

AllCommentsChangesGit/SVN commitsRelated reports
 [2010-10-09 14:57 UTC] joaoptm78 at gmail dot com 
The search would have the choice on any of these operators (=, <=, >=), my previous example implied using <=
 [2010-10-09 15:01 UTC] rasmus@php.net 
The way the array is stored in shared memory in its binary 
state, it would have to be fetched and reconstructed anyway, 
so the difference between a native APC function and you simply 
calling apc_fetch() followed by doing an array_search() in 
your script will be minimal and not worth the hassle of 
implementing.
 [2010-10-09 16:01 UTC] joaoptm78 at gmail dot com 
Ok, I understand a native APC function won't help now, but what about a native PHP function to search an array in a binary search fashion for operators <= and >= ?

Anyway would a native PHP function be faster than a for loop in this case?
 [2010-10-09 16:10 UTC] rasmus@php.net 
The binary search would be slightly faster as a native 
function, but not all that much.  The nice thing about a 
binary search is that it doesn't need to do very many lookups.  
The most time-consuming part of a binary search is the 
requirement that the array has to be sorted, so usually the 
sorting is what takes time.
 
PHP Copyright © 2001-2024 The PHP Group
All rights reserved. 		Last updated: Sat Dec 21 14:01:32 2024 UTC