summaryrefslogtreecommitdiff
path: root/libstd/search.myr
blob: 725e4196c2f3f9078cc3ac2bc624470b5c9e4070 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
use "cmp.use"
use "option.use"

pkg std =
	generic lsearch	: (sl : @t[:], val : @t, cmp : (a : @t, b : @t -> order) -> option(@idx::(integral,numeric)))
	generic bsearch	: (sl : @t[:], val : @t, cmp : (a : @t, b : @t -> order) -> option(@idx::(integral,numeric)))
;;

/* linear search over a list of values */
generic lsearch = {sl, val, cmp
	var i

	for i = 0; i < sl.len; i++
		match cmp(sl[i], val)
		| `Equal:
			-> `Some i
		| _:
			/* nothing */
		;;
	;;
	-> `None
}

/* binary search over a sorted list of values. */
generic bsearch  = {sl, val, cmp
	var hi, lo, mid

	lo = 0
	hi = sl.len - 1

	while lo <= hi
		mid = (hi + lo) / 2
		match cmp(val, sl[mid])
		| `Before:	hi = mid - 1
		| `After:	lo = mid + 1
		| `Equal:	
			-> `Some mid
		;;
	;;
	-> `None
}