forked from jgurtowski/ectools
-
Notifications
You must be signed in to change notification settings - Fork 0
/
algorithm.py
49 lines (40 loc) · 1.18 KB
/
algorithm.py
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
44
45
46
47
48
49
import sys
def binarySearch(inlist, cmp_func, first=0, last=None):
'''Returns index of first item that cmp_func returns 0.
None if can't be found
cmp_func is < 0 if the value you are looking for is
less than what is passed to cmp_func by this function.
> 0 if it is more, 0 if equal.
'''
last = len(inlist)-1 if not last else last
if last < first:
return None
mid = (last + first) / 2
d = cmp_func(inlist[mid])
if d < 0:
last = mid - 1
elif d > 0:
first = mid + 1
else:
return mid
return binarySearch(inlist, cmp_func, first, last)
def expandRegion(inlist, cmp_func, start=0):
'''Expands a region in a list based on cmp_func
While cmp_func returns true keep adding to region
returns a tuple (first,last) for boundaries of
the region
'''
if not cmp_func(inlist[start]):
return None
first = start
last = start
while first > 0:
if not cmp_func(inlist[first-1]):
break
first -= 1
ll = len(inlist)
while last < (ll-1):
if not cmp_func(inlist[last+1]):
break
last += 1
return (first,last)