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