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
Welcome back! If you're the original bug submitter, here's where you can edit the bug or add additional notes.
If you forgot your password, you can retrieve your password here.
Password:
Status:
Package:
Bug Type:
Summary:
From: joaoptm78 at gmail dot com
New email:
PHP Version: OS:

 

 [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 15:01:29 2024 UTC