diff options
| -rw-r--r-- | lib/pure/algorithm.nim | 27 |
1 files changed, 24 insertions, 3 deletions
diff --git a/lib/pure/algorithm.nim b/lib/pure/algorithm.nim index 4f7880fec..5d7348b8d 100644 --- a/lib/pure/algorithm.nim +++ b/lib/pure/algorithm.nim @@ -69,7 +69,7 @@ proc reversed*[T](a: openArray[T]): seq[T] = proc binarySearch*[T](a: openArray[T], key: T): int = ## binary search for `key` in `a`. Returns -1 if not found. - if ((a.len - 1) and a.len) == 0: + if ((a.len - 1) and a.len) == 0 and a.len > 0: # when `a.len` is a power of 2, a faster div can be used. var step = a.len div 2 while step > 0: @@ -367,10 +367,11 @@ when isMainModule: var srt1 = [1,2,3,4,4,4,4,5] var srt2 = ["iello","hello"] var srt3 = [1.0,1.0,1.0] - var srt4: seq[int] = @[] + var srt4: seq[int] assert srt1.isSorted(cmp) == true assert srt2.isSorted(cmp) == false assert srt3.isSorted(cmp) == true + assert srt4.isSorted(cmp) == true var srtseq = newSeq[int]() assert srtseq.isSorted(cmp) == true # Tests for reversed @@ -518,4 +519,24 @@ when isMainModule: block fillEmptySeq: var s = newSeq[int]() - s.fill(0) \ No newline at end of file + s.fill(0) + + block testBinarySearch: + var noData: seq[int] + doAssert binarySearch(noData, 7) == -1 + let oneData = @[1] + doAssert binarySearch(oneData, 1) == 0 + doAssert binarySearch(onedata, 7) == -1 + let someData = @[1,3,4,7] + doAssert binarySearch(someData, 1) == 0 + doAssert binarySearch(somedata, 7) == 3 + doAssert binarySearch(someData, -1) == -1 + doAssert binarySearch(someData, 5) == -1 + doAssert binarySearch(someData, 13) == -1 + let moreData = @[1,3,5,7,4711] + doAssert binarySearch(moreData, -1) == -1 + doAssert binarySearch(moreData, 1) == 0 + doAssert binarySearch(moreData, 5) == 2 + doAssert binarySearch(moreData, 6) == -1 + doAssert binarySearch(moreData, 4711) == 4 + doAssert binarySearch(moreData, 4712) == -1 |