From 28179e084e0c45137d62b4fe7b8dc9826bfd2fab Mon Sep 17 00:00:00 2001 From: dusoleil Date: Sun, 1 Aug 2021 23:25:54 -0400 Subject: Adding Various Small Tools Signed-off-by: dusoleil --- tools/bsearch.py | 44 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 44 insertions(+) create mode 100644 tools/bsearch.py (limited to 'tools/bsearch.py') diff --git a/tools/bsearch.py b/tools/bsearch.py new file mode 100644 index 0000000..1c92343 --- /dev/null +++ b/tools/bsearch.py @@ -0,0 +1,44 @@ +#binary search +#searches for an s in i that satisfies x == f(i[s]) +#i = iterable +#f = function to call on each element of i +#x = value to search for +#start = offset into iterable to start +#end = offset into iterable to end +#if it finds a match, it returns a tuple of (s,i[s],f(i[s])) +#if it does not find a match, it returns (-1,None,None) +def bsearch(i,f,x,start=0,end=-1): + if end == -1: + end = len(i)-1 + #s = _bsearch(i,f,start,end,x) + s = _bsearch2(i,f,start,end,x) + return (s,i[s],f(i[s])) if s != -1 else (s,None,None) + +#recursive +def _bsearch(i,f,lo,hi,x): + if hi >= lo: + md = (hi+lo)//2 + a = f(i[md]) + if a == x: + return md + elif a > x: + return _bsearch(i,f,lo,md-1,x) + else: + return _bsearch(i,f,md+1,hi,x) + else: + return -1 + +#loop +def _bsearch2(i,f,lo,hi,x): + while True: + if hi >= lo: + md = (hi+lo)//2 + a = f(i[md]) + if a == x: + return md + elif a > x: + hi = md-1 + else: + lo = md+1 + else: + return -1 -- cgit v1.2.3