Binary search: Difference between revisions
→{{header|Zig}}: Add recursive example with indexes
(Add Zig examples using slices or indexes, for now iterative only.) |
(→{{header|Zig}}: Add recursive example with indexes) |
||
Line 8,013:
====Iterative====
<syntaxhighlight lang="zig">const
pub fn binarySearch(comptime T: type,
if (@sizeOf(T) == 0) {
return if (
}
var low: usize = 0;
var high: usize =
return while (low <= high) {
const mid = ((high - low) / 2) + low;
const mid_elem: T =
if (mid_elem > search_value)
high =
else if (mid_elem < search_value)
low = mid + 1
Line 8,032:
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 {
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 (@sizeOf(T) == 0) {
return if (input.len != 0) &input[0] else null;
}
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>
|