Concatenative topics
Concatenative meta
Other languages
Meta
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.
@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
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) ;
This revision created on Tue, 12 Mar 2024 06:01:24 by CapitalEx (Add factor)