Binary Search is a searching algorithm used in a sorted array by repeatedly dividing the search interval in half. The idea of binary search is to use the information that the array is sorted and reduce the time complexity to O(log N).

Create an array 02 03 04 10 40, and find the offset from 0 of the array or return -1 when the value is not found.

Uxntal

@on-reset ( -> )
	( l ) #0000 
	( r ) ;arr/end ;arr SUB2 #0001 SUB2 
	( array* target ) ;arr #04 binsearch
	( print result ) #010e DEO
	BRK

@arr 02 03 04 10 40 &end

@binsearch ( l* r* arr* x -- addr* )
	,&x STR
	STH2
	&>w ( l* r* | arr* -- addr* )
		( m* ) OVR2 SUB2k #01 SFT ADD2
		( m* arr+m* ) DUP2 STH2kr ADD2
		( m* arr[m] x ) LDA [ LIT &x $1 ]
		( arr[m] == x ) NEQk ?{ POP2 POP2r NIP2 NIP2 JMP2r }
		( arr[m] < x ) GTH ?{ INC2 ROT2 POP2 SWP2 !& }
		( else ) #0001 SUB2 NIP2 
		& GTH2k #00 EQU ?&>w
	POP2 POP2 POP2r #ffff JMP2r

Factor

USING: combinators kernel math math.order sequences ;
IN: catlang-discord.challenges.binary-search

DEFER: (binary-search)

: search-hi ( obj seq hi lo -- i/f )
    over + 2/ 1 + (binary-search) ;

: search-lo ( obj seq hi lo -- i/f )
    tuck + 2/ 1 - swap (binary-search) ;

: test-midpoint ( obj seq hi lo -- obj seq hi lo ord )
    2dup + 2/ '[ 2dup _ swap nth <=> ] 2dip rot ;

: search-step ( obj seq hi lo -- i/f )
    test-midpoint {
        { +lt+ [ search-lo ] }
        { +eq+ [ + 2/ 2nip ] }
        { +gt+ [ search-hi ] }
    } case ;

: (binary-search) ( obj seq hi lo -- i/-1 )
    2dup < [ 4drop -1 ] [ search-step ] if ;

: binary-search ( seq obj -- i/f )
    swap dup length 1 - 0 (binary-search) ;