Binary search: Difference between revisions

Binary search (view source)

Revision as of 13:49, 3 March 2024

5,574 bytes added , 2 months ago

Add bruijn

Marvin

55

edits

Revision as of 00:19, 25 July 2023 (view source) Christophoro S (talk \| contribs) (→‎{{header\|Modula-2}}: Added a solution.) ← Older edit		Revision as of 13:49, 3 March 2024 (view source) Marvin (talk \| contribs) (Add bruijn) Newer edit →
(11 intermediate revisions by 7 users not shown)
Line 2,519: { p "Not found" } { p "Found at index: #{index}" }</syntaxhighlight> =={{header\|Bruijn}}== <syntaxhighlight lang="bruijn"> :import std/Combinator . :import std/Math . :import std/List . :import std/Option . binary-search [y [[[[[2 <? 3 none go]]]]] (+0) --(∀0) 0] go [compare-case eq lt gt (2 !! 0) 1] /²(3 + 2) eq some 0 lt 5 4 --0 2 1 gt 5 ++0 3 2 1 # example using sorted list of x^3, x=[-50,50] find [[map-or "not found" [0 : (1 !! 0)] (binary-search 0 1)] lst] lst take (+100) ((\pow (+3)) <$> (iterate ++‣ (-50))) :test (find (+100)) ("not found") :test ((head (find (+125))) =? (+55)) ([[1]]) :test ((head (find (+117649))) =? (+99)) ([[1]]) </syntaxhighlight> =={{header\|C}}== Line 3,194 ⟶ 3,217: =={{header\|EasyLang}}== <syntaxhighlight lang="text"> proc ~~bin_search~~binSearch val . a[] res . low = 1 high = len a[] res = 0 while low <= high and res = 0 mid = (low + high) div 2 if a[mid] > val high = mid - 1 elif a[mid] < val low = mid + 1 else res = mid . . . a[] = [ 2 4 6 8 9 ] ~~call bin_search~~binSearch 8 a[] r print r </syntaxhighlight> Line 4,542 ⟶ 4,565: ]</pre> =={{header\|jq}}== {{works with\|jq}} If the input array is sorted, then binarySearch(value) as defined here will return an index (i.e. offset) of value in the array if the array contains the value, and otherwise (-1 - ix), where ix is the insertion point, if the value cannot be found. binarySearch will always terminate. '''Also works with gojq, the Go implementation of jq''' ~~Recursive solution:<syntaxhighlight lang="jq">def binarySearch(value):~~ jq and gojq both have a binary-search builtin named `bsearch`. In the following, a parameterized filter for performing a binary search of a sorted JSON array is defined. Specifically, binarySearch(value) will return an index (i.e. offset) of `value` in the array if the array contains the value, and otherwise (-1 - ix), where ix is the insertion point, if the value cannot be found. binarySearch will always terminate. The inner function is recursive. <syntaxhighlight lang="jq">def binarySearch(value): # To avoid copying the array, simply pass in the current low and high offsets def binarySearch(low; high): Line 4,558 ⟶ 4,589: {{Out}} 2 =={{header\|Jsish}}== <syntaxhighlight lang="javascript">/** Line 4,954 ⟶ 4,986: </syntaxhighlight> =={{header\|MACRO-11}}== This deals with the overflow problem when calculating `mid` by using a `ROR` (rotate right) instruction to divide by two, which rotates the carry flag back into the result. `ADD` produces a 17-bit result, with the 17th bit in the carry flag. <syntaxhighlight lang="macro11"> .TITLE BINRTA .MCALL .TTYOUT,.PRINT,.EXIT ; TEST CODE BINRTA::CLR R5 1$: MOV R5,R0 ADD #'0,R0 .TTYOUT MOV R5,R0 MOV #DATA,R1 MOV #DATEND,R2 JSR PC,BINSRC BEQ 2$ .PRINT #4$ BR 3$ 2$: .PRINT #5$ 3$: INC R5 CMP R5,#^D10 BLT 1$ .EXIT 4$: .ASCII / NOT/ 5$: .ASCIZ / FOUND/ .EVEN ; TEST DATA DATA: .WORD 1, 2, 3, 5, 7 DATEND = . + 2 ; BINARY SEARCH ; INPUT: R0 = VALUE, R1 = LOW PTR, R2 = HIGH PTR ; OUTPUT: ZF SET IF VALUE FOUND; R1 = INSERTION POINT BINSRC: BR 3$ 1$: MOV R1,R3 ADD R2,R3 ROR R3 CMP (R3),R0 BGE 2$ ADD #2,R3 MOV R3,R1 BR 3$ 2$: SUB #2,R3 MOV R3,R2 3$: CMP R2,R1 BGE 1$ CMP (R1),R0 RTS PC .END BINRTA</syntaxhighlight> {{out}} <pre>0 NOT FOUND 1 FOUND 2 FOUND 3 FOUND 4 NOT FOUND 5 FOUND 6 NOT FOUND 7 FOUND 8 NOT FOUND 9 NOT FOUND</pre> =={{header\|Maple}}== The calculation of "mid" cannot overflow, since Maple uses arbitrary precision integer arithmetic, and the largest list or array is far, far smaller than the effective range of integers. Line 5,010 ⟶ 5,104: > PP[ 3 ]; 13</syntaxhighlight> =={{header\|Mathematica}} / {{header\|Wolfram Language}}== '''Recursive''' Line 6,571 ⟶ 6,666: } }</syntaxhighlight> ~~=={{header\|REXX}}==~~ =={{header\|REXX}}== ===recursive version=== Line 7,756 ⟶ 7,851: ]</syntaxhighlight> =={{header\|Wren}}== <syntaxhighlight lang="~~ecmascript~~wren">class BinarySearch { static recursive(a, value, low, high) { if (high < low) return -1 Line 7,817 ⟶ 7,912: 70 was not found in the array. </pre> =={{header\|XPL0}}== {{trans\|C}} Line 7,906 ⟶ 8,002: LOCRL R2,R1 Low? => LOW = MID+1 J LOOP }</syntaxhighlight> =={{header\|Zig}}== '''Works with:''' 0.11.x, 0.12.0-dev.1381+61861ef39 For 0.10.x, replace @intFromPtr(...) with @ptrToInt(...) in these examples. ===With slices=== ====Iterative==== <syntaxhighlight lang="zig">pub fn binarySearch(comptime T: type, input: []const T, search_value: T) ?usize { if (input.len == 0) return null; if (@sizeOf(T) == 0) return 0; var view: []const T = input; const item_ptr: const T = item_ptr: while (view.len > 0) { const mid = (view.len - 1) / 2; const mid_elem_ptr: const T = &view[mid]; if (mid_elem_ptr.* > search_value) view = view[0..mid] else if (mid_elem_ptr.* < search_value) view = view[mid + 1 .. view.len] else break :item_ptr mid_elem_ptr; } else return null; const distance_in_bytes = @intFromPtr(item_ptr) - @intFromPtr(input.ptr); return (distance_in_bytes / @sizeOf(T)); }</syntaxhighlight> ====Recursive==== <syntaxhighlight lang="zig">pub fn binarySearch(comptime T: type, input: []const T, search_value: T) ?usize { return binarySearchInner(T, input, search_value, @intFromPtr(input.ptr)); } fn binarySearchInner(comptime T: type, input: []const T, search_value: T, start_address: usize) ?usize { if (input.len == 0) return null; if (@sizeOf(T) == 0) return 0; const mid = (input.len - 1) / 2; const mid_elem_ptr: const T = &input[mid]; return if (mid_elem_ptr. > search_value) binarySearchInner(T, input[0..mid], search_value, start_address) else if (mid_elem_ptr.* < search_value) binarySearchInner(T, input[mid + 1 .. input.len], search_value, start_address) else (@intFromPtr(mid_elem_ptr) - start_address) / @sizeOf(T); }</syntaxhighlight> ===With indexes=== ====Iterative==== <syntaxhighlight lang="zig">const math = @import("std").math; pub fn binarySearch(comptime T: type, input: []const T, search_value: T) ?usize { if (input.len == 0) return null; if (@sizeOf(T) == 0) return 0; var low: usize = 0; var high: usize = input.len - 1; return while (low <= high) { const mid = ((high - low) / 2) + low; const mid_elem: T = input[mid]; if (mid_elem > search_value) high = math.sub(usize, mid, 1) catch break null else if (mid_elem < search_value) low = mid + 1 else break mid; } else null; }</syntaxhighlight> ====Recursive==== <syntaxhighlight lang="zig">const math = @import("std").math; pub fn binarySearch(comptime T: type, input: []const T, search_value: T) ?usize { if (input.len == 0) return null; if (@sizeOf(T) == 0) return 0; return binarySearchInner(T, input, search_value, 0, input.len - 1); } fn binarySearchInner(comptime T: type, input: []const T, search_value: T, low: usize, high: usize) ?usize { if (low > high) return null; const mid = ((high - low) / 2) + low; const mid_elem: T = input[mid]; return if (mid_elem > search_value) binarySearchInner(T, input, search_value, low, math.sub(usize, mid, 1) catch return null) else if (mid_elem < search_value) binarySearchInner(T, input, search_value, mid + 1, high) else mid; }</syntaxhighlight> =={{header\|zkl}}== This algorithm is tail recursive, which means it is both recursive and iterative (since tail recursion optimizes to a jump). Overflow is not possible because Ints (64 bit) are a lot bigger than the max length of a list.