[m-rev.] For review: add array.binary_search

[Ralph Becket]

As requested by Paul:


Estimated hours taken: 1
Branches: main

library/array.m:
	Add array.binary_search/3.
		
NEWS:
	Mention the new predicate.

Index: NEWS
===================================================================
RCS file: /home/mercury1/repository/mercury/NEWS,v
retrieving revision 1.509
diff -u -r1.509 NEWS
--- NEWS	11 May 2009 05:24:08 -0000	1.509
+++ NEWS	17 Jun 2009 04:18:22 -0000
@@ -98,6 +98,7 @@
 * The following predicates have been added to the array modules:
     array.fold/4
     array.foldl2/6
+    array.binary_search/3
     version_array.foldl/4
 
 * The following predicates have been added to the list module:
Index: library/array.m
===================================================================
RCS file: /home/mercury1/repository/mercury/library/array.m,v
retrieving revision 1.164
diff -u -r1.164 array.m
--- library/array.m	5 Jun 2009 04:17:10 -0000	1.164
+++ library/array.m	17 Jun 2009 04:17:23 -0000
@@ -407,6 +407,17 @@
 %:- mode array.foldr(func(in, di) = uo is det, array_ui, di) = uo is det.
 :- mode array.foldr(func(in, di) = uo is det, in, di) = uo is det.
 
+    % array.binary_search(A, X, I) performs a binary search for X in array A,
+    % computing I as the result.  More specifically, if the call succeeds, then
+    % either A ^ elem(I) = X or A ^ elem(I) @< X and either
+    % X @< A ^ elem(I + 1) or I is the last index in A.
+    %
+    % A must be sorted into ascending order (but may contain duplicates).
+    %
+:- pred array.binary_search(array(T), T, int).
+:- mode array.binary_search(array_ui, in, out) is semidet.
+
     % array.random_permutation(A0, A, RS0, RS) permutes the elements in
     % A0 given random seed RS0 and returns the permuted array in A
     % and the next random seed in RS.
@@ -418,6 +429,7 @@
     % Convert an array to a pretty_printer.doc for formatting.
     %
 :- func array.array_to_doc(array(T)) = pretty_printer.doc.
+:- mode array.array_to_doc(array_ui) = out is det.
 
 %-----------------------------------------------------------------------------%
 %-----------------------------------------------------------------------------%
@@ -1475,6 +1487,35 @@
 
 %------------------------------------------------------------------------------%
 
+array.binary_search(A, X, I) :-
+    Lo = 0,
+    Hi = array.size(A) - 1,
+    binary_search_2(A, X, Lo, Hi, I).
+
+:- pred binary_search_2(array(T), T, int, int, int).
+:- mode binary_search_2(array_ui, in, in, in, out) is semidet.
+
+binary_search_2(A, X, Lo, Hi, I) :-
+    Lo =< Hi,
+    Mid = (Lo + Hi) / 2,
+    O = ordering(A ^ elem(Mid), X),
+    (
+        O = (>),
+        binary_search_2(A, X, Lo, Mid - 1, I)
+    ;
+        O = (=),
+        I = Mid
+    ;
+        O = (<),
+        ( if Mid < Hi, X @< A ^ elem(Mid + 1) then
+            I = Mid
+          else
+            binary_search_2(A, X, Mid + 1, Hi, I)
+        )
+    ).
+
+%-----------------------------------------------------------------------------%
+
 array.random_permutation(A0, A, RS0, RS) :-
     Lo = array.min(A0),
     Hi = array.max(A0),
--------------------------------------------------------------------------
mercury-reviews mailing list
Post messages to:       mercury-reviews at csse.unimelb.edu.au
Administrative Queries: owner-mercury-reviews at csse.unimelb.edu.au
Subscriptions:          mercury-reviews-request at csse.unimelb.edu.au
--------------------------------------------------------------------------