Binary search: Difference between revisions
Add Zig examples using slices or indexes, for now iterative only.
(Add Zig examples using slices or indexes, for now iterative only.) |
|||
Line 7,978:
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 (@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}}==
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.
| |||