Binary search: Difference between revisions
→Python: Recursive: Added a version generalising binary sort from direct matches to the use of custom comparator functions.
(→Python: Recursive: Added a version generalising binary sort from direct matches to the use of custom comparator functions.) |
|||
Line 3,878:
elif l[mid] < value: return binary_search(l, value, mid+1, high)
else: return mid</lang>
We can also generalize this kind of binary search from direct matches to searches using a custom comparator function.
In addition to a search for a particular word in an AZ-sorted list, for example, we could also perform a binary search for a word of a given '''length''' (in a word-list sorted by rising length), or for a particular value of any other comparable property of items in a suitably sorted list:
<lang python># findIndexBinary :: (a -> Ordering) -> [a] -> Maybe Int
def findIndexBinary(p):
def go(xs):
def bin(lo, hi):
if hi < lo:
return None
else:
mid = (lo + hi) // 2
cmp = p(xs[mid])
return bin(lo, mid - 1) if -1 == cmp else (
bin(mid + 1, hi) if 1 == cmp else (
mid
)
)
n = len(xs)
return bin(0, n - 1) if xs else None
return lambda xs: go(xs)
# COMPARISON CONSTRUCTORS ---------------------------------
# compare :: a -> a -> Ordering
def compare(a):
'''Simple comparison of x and y -> LT|EQ|GT'''
return lambda b: -1 if a < b else (1 if a > b else 0)
# byKV :: (a -> b) -> a -> a -> Ordering
def byKV(f):
'''Property accessor function -> target value -> x -> LT|EQ|GT'''
def go(v, x):
fx = f(x)
return 1 if fx < v else -1 if fx > v else 0
return lambda v: lambda x: go(v, x)
# TESTS ---------------------------------------------------
def main():
# BINARY SEARCH FOR WORD IN AZ-SORTED LIST
mb1 = findIndexBinary(compare('mu'))(
# Sorted AZ
['alpha', 'beta', 'delta', 'epsilon', 'eta', 'gamma', 'iota',
'kappa', 'lambda', 'mu', 'theta', 'zeta']
)
print (
'Not found' if None is mb1 else (
'Word found at index ' + str(mb1)
)
)
# BINARY SEARCH FOR WORD OF GIVEN LENGTH (IN WORD-LENGTH SORTED LIST)
mb2 = findIndexBinary(byKV(len)(6))(
# Sorted by rising length
['mu', 'eta', 'beta', 'iota', 'zeta', 'alpha', 'delta', 'gamma',
'kappa', 'theta', 'lambda', 'epsilon']
)
print (
'Not found' if None is mb2 else (
'Word of given length found at index ' + str(mb2)
)
)
if __name__ == '__main__':
main()</lang>
{{}}
<pre></pre>
===Python: Library===
| |||