Binary search: Difference between revisions
→{{header|Zig}}: Add recursive example with slices
(→{{header|Zig}}: Add recursive example with indexes) |
(→{{header|Zig}}: Add recursive example with slices) |
||
Line 7,989:
====Iterative====
<syntaxhighlight lang="zig">pub fn binarySearch(comptime T: type, input: []const T, search_value: T) ?usize {
if (
}▼
var view: []const T = input;
Line 8,008 ⟶ 8,007:
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 {
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)
(@intFromPtr(mid_elem_ptr) - start_address) / @sizeOf(T);
}</syntaxhighlight>
Line 8,016 ⟶ 8,036:
pub fn binarySearch(comptime T: type, input: []const T, search_value: T) ?usize {
if (
var low: usize = 0;
Line 8,038 ⟶ 8,057:
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 (@sizeOf(T) == 0) {
▲ return if (input.len != 0) &input[0] else null;
if (low > high) return null;
| |||