|  support |  documentation |  report a bug |  advanced search |  search howto |  statistics |  random bug |  login
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 Add Comment Developer Edit
Anyone can comment on a bug. Have a simpler test case? Does it work for you on a different platform? Let us know!
Just going to say 'Me too!'? Don't clutter the database with that please — but make sure to vote on the bug!
Your email address:
Solve the problem:
1 + 40 = ?
Subscribe to this entry?

 [2010-10-09 14:52 UTC] joaoptm78 at gmail dot com
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.

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.


Add a Patch

Pull Requests

Add a Pull Request


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]
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 
 [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]
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: Thu May 30 16:01:33 2024 UTC