Binary search: Difference between revisions
Content added Content deleted
(Add Zig examples using slices or indexes, for now iterative only.) |
|||
| Line 7,978: | Line 7,978: | ||
LOCRL R2,R1 Low? => LOW = MID+1 |
LOCRL R2,R1 Low? => LOW = MID+1 |
||
J LOOP }</syntaxhighlight> |
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 (@sizeOf(T) == 0) { |
|||
return if (input.len != 0) &input[0] else null; |
|||
} |
|||
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> |
|||
===With indexes=== |
|||
====Iterative==== |
|||
<syntaxhighlight lang="zig">const std = @import("std"); |
|||
fn binarySearch(comptime T: type, arr: []const T, search_value: T) ?usize { |
|||
if (@sizeOf(T) == 0) { |
|||
return if (arr.len != 0) &arr[0] else null; |
|||
} |
|||
var low: usize = 0; |
|||
var high: usize = arr.len - 1; |
|||
return while (low <= high) { |
|||
const mid = ((high - low) / 2) + low; |
|||
const mid_elem: T = arr[mid]; |
|||
if (mid_elem > search_value) |
|||
high = std.math.sub(usize, mid, 1) catch break null |
|||
else if (mid_elem < search_value) |
|||
low = mid + 1 |
|||
else |
|||
break mid; |
|||
} else null; |
|||
}</syntaxhighlight> |
|||
=={{header|zkl}}== |
=={{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. |
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. |
||