Binary search: Difference between revisions

Line 8,013:

====Iterative====

<syntaxhighlight lang="zig">const ~~std~~ = @import("std");

<syntaxhighlight lang="zig">const math = @import("std").math;

fn binarySearch(comptime T: type, ~~arr~~: []const T, search_value: T) ?usize {

pub fn binarySearch(comptime T: type, input: []const T, search_value: T) ?usize {

if (@sizeOf(T) == 0) {

return if (~~arr~~.len != 0) &~~arr~~[0] else null;

return if (input.len != 0) &input[0] else null;

}

var low: usize = 0;

var high: usize = ~~arr~~.len - 1;

var high: usize = input.len - 1;

return while (low <= high) {

const mid = ((high - low) / 2) + low;

const mid_elem: T = ~~arr~~[mid];

const mid_elem: T = input[mid];

if (mid_elem > search_value)

high = ~~std.~~math.sub(usize, mid, 1) catch break null

high = math.sub(usize, mid, 1) catch break null

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>