bsearch as C-coded builtin #527
Description
As best I can tell, based on my timings on a Mac, a jq-coded binary search algorithm on a sorted array can't compete even with the C-coded linear search. The jq version of bsearch that I used is appended.
Thus I would like to request a C-coded bsearch that would always terminate and that would return the index of the item if the array is sorted (as per sort). I realize that such a function would be unusual, but one can say "it is what it is".
The only satisfactory alternative that I can think of (#517) has already been effectively rejected.
# binary search
# requires last/1
# WARNING: If the input is not sorted as per sort, bsearch will terminate but with
# irrelevant results.
#
def bsearch(target):
if length == 0 then null
elif length == 1 then (if .[0] == target then 0 else null end)
else . as $in
# state variable: [start, end, answer]
# where start and end are the upper and lower offsets to use.
| last( [0, length-1, null]
| while ( .[0] <= .[1] ;
(if .[2] != null then (.[1] = -1) # i.e. break
else
( ( (.[1] + .[0]) / 2 ) | floor ) as $mid
| $in[$mid] as $monkey
| if $monkey == target then (.[2] = $mid) # success
elif .[0] == .[1] then (.[1] = -1) # failure
elif $monkey < target then (.[0] = ($mid + 1))
else (.[1] = ($mid - 1))
end
end ))) | .[2]
end;