From 444d1e5f3e9a39759079736302e3404018141b02 Mon Sep 17 00:00:00 2001 From: Scott Date: Wed, 26 Jan 2022 11:26:55 -0800 Subject: [PATCH] Make sanity check optional. --- list_utils.py | 24 ++++++++++++++---------- 1 file changed, 14 insertions(+), 10 deletions(-) diff --git a/list_utils.py b/list_utils.py index 1b27436..b877e38 100644 --- a/list_utils.py +++ b/list_utils.py @@ -197,7 +197,7 @@ def ngrams(lst: Sequence[Any], n): ['an', 'awesome', 'test'] """ for i in range(len(lst) - n + 1): - yield lst[i:i + n] + yield lst[i : i + n] def permute(seq: Sequence[Any]): @@ -224,12 +224,12 @@ def _permute(seq: Sequence[Any], path): for i in range(len(seq)): car = seq[i] left = seq[0:i] - right = seq[i + 1:] + right = seq[i + 1 :] cdr = left + right yield from _permute(cdr, path + car) -def binary_search(lst: Sequence[Any], target: Any) -> Tuple[bool, int]: +def binary_search(lst: Sequence[Any], target: Any, *, sanity_check=False) -> Tuple[bool, int]: """Performs a binary search on lst (which must already be sorted). Returns a Tuple composed of a bool which indicates whether the target was found and an int which indicates the index closest to @@ -249,21 +249,24 @@ def binary_search(lst: Sequence[Any], target: Any) -> Tuple[bool, int]: (False, 1) >>> a.append(9) - >>> binary_search(a, 4) + >>> binary_search(a, 4, sanity_check=True) Traceback (most recent call last): ... AssertionError """ - last = None - for x in lst: - if last is not None: - assert x >= last # This asserts iff the list isn't sorted - last = x # in ascending order. + if sanity_check: + last = None + for x in lst: + if last is not None: + assert x >= last # This asserts iff the list isn't sorted + last = x # in ascending order. return _binary_search(lst, target, 0, len(lst) - 1) -def _binary_search(lst: Sequence[Any], target: Any, low: int, high: int) -> Tuple[bool, int]: +def _binary_search( + lst: Sequence[Any], target: Any, low: int, high: int +) -> Tuple[bool, int]: if high >= low: mid = (high + low) // 2 if lst[mid] == target: @@ -278,4 +281,5 @@ def _binary_search(lst: Sequence[Any], target: Any, low: int, high: int) -> Tupl if __name__ == '__main__': import doctest + doctest.testmod() -- 2.45.2