bsearch(x) (binary search): builtin.c (tested), with documentation and test case. Always yields an integer (even if input is unsorted); returns (-1 - ix) if x is not in input array.

3 files changed, 58 insertions, 0 deletions

diff --git a/builtin.c b/builtin.c
index c9b1868f..25879e3f 100644
--- a/builtin.c
+++ b/builtin.c
@@ -1161,6 +1161,37 @@ static const char* const jq_builtins[] = {
   // # like ruby's upcase - only characters a to z are affected
   "def ascii_upcase:"
   "  explode | map( if 97 <= . and . <= 122 then . - 32  else . end) | implode;",
+
+  // # Assuming the input array is sorted, bsearch/1 returns
+  // # the index of the target if the target is in the input array; and otherwise
+  // #  (-1 - ix), where ix is the insertion point that would leave the array sorted.
+  // # If the input is not sorted, bsearch will terminate but with irrelevant results.
+  "def bsearch(target):"
+  "  if length == 0 then -1"
+  "  elif length == 1 then"
+  "     if target == .[0] then 0 elif target < .[0] then -1 else -2 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 )))"
+  "    | if .[2] == null then"         // # compute the insertion point
+  "         if $in[ .[0] ] < target then (-2 -.[0])"
+  "         else (-1 -.[0])"
+  "         end"
+  "      else .[2]"
+  "      end"
+  "  end;",
 };
 #undef LIBM_DD
 
diff --git a/docs/content/3.manual/manual.yml b/docs/content/3.manual/manual.yml
index cfd87c24..76231b8d 100644
--- a/docs/content/3.manual/manual.yml
+++ b/docs/content/3.manual/manual.yml
@@ -1461,6 +1461,29 @@ sections:
             output: ['[1,2],[null,3]']
 
 
+      - title: "`bsearch(x)`"
+        body: |
+
+          bsearch(x) conducts a binary search for x in the input
+          array.  If the input is sorted and contains x, then
+          bsearch(x) will return its index in the array; otherwise, if
+          the array is sorted, it will return (-1 - ix) where ix is an
+          insertion point such that the array would still be sorted
+          after the insertion of x at ix.  If the array is not sorted,
+          bsearch(x) will return an integer that is probably of no
+          interest.
+
+        examples:
+          - program: 'bsearch(0)'
+            input: '[0,1]'
+            output: ['0']
+          - program: 'bsearch(0)'
+            input: '[1,2,3]'
+            output: ['-1']
+          - program: 'bsearch(4) as $ix | if $ix < 0 then .[-(1+$ix)] = 4 else . end'
+            input: '[1,2,3]'
+            output: ['[1,2,3,4]']
+
       - title: "String interpolation - `\\(foo)`"
         body: |
 
diff --git a/tests/all.test b/tests/all.test
index f632e43e..d7bff455 100644
--- a/tests/all.test
+++ b/tests/all.test
@@ -1111,3 +1111,7 @@ transpose
 ascii_upcase
 "useful but not for é"
 "USEFUL BUT NOT FOR é"
+
+bsearch(4)
+[1,2,3]
+-4