1/*  Part of SWI-Prolog odf-sheet pack
    2
    3    Author:        Jan Wielemaker
    4    E-mail:        J.Wielemaker@vu.nl
    5    WWW:           http://www.swi-prolog.org/pack/list?p=odf-sheet
    6
    7    Copyright (c) 2012-2014, VU University of Amsterdam
    8    All rights reserved.
    9
   10    Redistribution and use in source and binary forms, with or without
   11    modification, are permitted provided that the following conditions are
   12    met:
   13
   14    1. Redistributions of source code must retain the above copyright
   15    notice, this list of conditions and the following disclaimer.
   16
   17    2. Redistributions in binary form must reproduce the above copyright
   18    notice, this list of conditions and the following disclaimer in the
   19    documentation and/or other materials provided with the distribution.
   20
   21    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
   22    IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
   23    TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
   24    PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
   25    HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
   26    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
   27    TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
   28    PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
   29    LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
   30    NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
   31    SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
   32*/
   33
   34:- module(bisect,
   35	  [ bisect/4				% :Test, +Low, +High, -LowestFail
   36	  ]).

 bisect(:Test, +Low, +High, -LowestFail) is semidet

True when LowestFail is the lowest integer between Low and High for which call(Test,LowestFail) fails. Fails if call(Test,High) succeeds.

This predicate assumes that there is a Value such that call(Test,X) is true for all X in [Low..Value) and false for all X in [Value..High].

   48:- meta_predicate
   49	bisect(1, +, +, -).   50
   51bisect(Test, _, To, _) :-
   52	call(Test, To), !,
   53	fail.
   54bisect(Test, From, To, Last) :-
   55	bsect(Test, From, To, Last).
   56
   57:- meta_predicate
   58	bsect(1, +, +, -).   59
   60bsect(Test, From, To, Last) :-
   61	Mid is (From+To)//2,
   62	(   call(Test, Mid)
   63	->  (   Mid+1 >= To
   64	    ->	Last = To
   65	    ;	bsect(Test, Mid, To, Last)
   66	    )
   67	;   (   Mid == From
   68	    ->	Last = From
   69	    ;	bsect(Test, From, Mid, Last)
   70	    )
   71	)