binary_search
| Definition: | integer res = binary_search(object needle, sequence haystack, integer lo=1, hi=length(haystack), fn=0) |
| Description: |
Finds a needle in an ordered haystack.
needle: an object to look for haystack: an ordered sequence to be searched lo, hi: allow the limiting of processing to a specific range of haystack fn: a partition function, see below. Returns either a positive integer index, which means haystack[res]==needle, otherwise the negative index of where it would go were it inserted now. |
| pwa/p2js: | Supported. |
| Notes: |
Results are undefined if haystack is not in ascending order or contains duplicates. In the latter case (ie
ascending order with duplicates, which needle matches) it is guaranteed to locate one of the duplicates, but
it could be the first, last, or anything inbetween. In some cases it may still be useful to get the "any", and
then explicitly/manually step backward/forward to some edge of the consecutive-duplicates-slice.
A partition function fn(object needle, haystacki) can be provided which causes binary_search() to yield an always negative index such that haystack[lo..(-res)-1] (should) all yield true from fn(needle,haystack[i]), and haystack[-res..hi] all false. If the specified range of haystack does not yield <all true><all false> from fn() the results are undefined. The value passed in needle is forwarded to fn() but otherwise unused, and can therefore contain anything needed. Obviously this performs some log2(hi-lo) operations, which may be a significant improvement over hi-lo aka lo += 1. Take care not to use a negative result as a negative index, for instance in the following example 0 ==> -1 means "before s[1]" which is nowhere near s[-1] aka s[$]. |
| Example 1: |
?binary_search(0,{1,3,5}) -- -1
?binary_search(1,{1,3,5}) -- 1
?binary_search(2,{1,3,5}) -- -2
?binary_search(3,{1,3,5}) -- 2
?binary_search(4,{1,3,5}) -- -3
?binary_search(5,{1,3,5}) -- 3
?binary_search(6,{1,3,5}) -- -4
|
| Example 2: |
function partfun(integer needle, haystacki) return haystacki<needle end function ?binary_search(50,tagset(100),1,100,partfun) -- -50 -- (your responsibility to check haystack[abs(-50)]==50 || needs inserting) ?binary_search(0,tagset(100),1,100,partfun) -- -1 ( < all) ?binary_search(1,tagset(100),1,100,partfun) -- -1 (== first, note) ?binary_search(100,tagset(100),fn:=partfun) -- -100 (== last, maybe) ?binary_search(101,tagset(100),fn:=partfun) -- -101 ( > all) |
| Implementation: |
See builtins\bsearch.e (an autoinclude) for details of the actual implementation. hi is actually defaulted to -1, which is then replaced with length(haystack), for p2js compatibility reasons. |
| See Also: | find |