diff options
Diffstat (limited to 'lib')
| -rwxr-xr-x | lib/pure/algorithm.nim | 18 |
1 files changed, 18 insertions, 0 deletions
diff --git a/lib/pure/algorithm.nim b/lib/pure/algorithm.nim index 1e9a0bb4b..045b78250 100755 --- a/lib/pure/algorithm.nim +++ b/lib/pure/algorithm.nim @@ -34,6 +34,24 @@ proc reverse*[T](a: var openArray[T]) = ## reverses the array `a`. reverse(a, 0, a.high) +proc binarySearch*[T](a: openarray[T], key: T): int = + ## binary search for `key` in `a`. Returns -1 if not found. + var b = len(a) + while result < b: + var mid = (result + b) div 2 + if a[mid] < key: result = mid + 1 + else: b = mid + if result >= len(x) or a[result] != key: result = -1 + +proc smartBinarySearch*[T](a: openArray[T], key: T): int = + ## ``a.len`` must be a power of 2 for this to work. + var step = a.len div 2 + while step > 0: + if a[result or step] <= key: + result = result or step + step = step shr 1 + if a[result] != key: result = -1 + const onlySafeCode = false |