Hi, my question is not specific to Nim but I'm asking it here because I'm using
it :)
I am debugging a simple iterative binary search but it seems to fail my test.
Here's my impl:
import options
proc index_of*[T](list: openArray[T]; key: T): Option[int] =
var
lo = list.low()
hi = list.high()
while hi > lo:
let mid: int = lo + (hi - lo).div(2)
if list[mid] < key:
lo = mid + 1
elif list[mid] > key:
hi = mid - 1
else:
return some(mid)
return none(int)
Run
My unittest:
import unittest, options
import cdsan/binary_search
test "binary_search":
let list = @[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
for item in list:
check index_of[int](list, item) == some(item)
Run
However my unittest fails witch cases below:
> /home/u9898287/proj/cdsan/tests/test1.nim(7, 36): Check failed:
> index_of[int](list, item) == some(item) index_of[int](list, item) was
> None[int] some(item) was Some(1)
> >/home/u9898287/proj/cdsan/tests/test1.nim(7, 36): Check failed:
> index_of[int](list, item) == some(item) index_of[int](list, item) was
> None[int] some(item) was Some(4)
> >/home/u9898287/proj/cdsan/tests/test1.nim(7, 36): Check failed:
> index_of[int](list, item) == some(item) index_of[int](list, item) was
> None[int] some(item) was Some(7)
> >/home/u9898287/proj/cdsan/tests/test1.nim(7, 36): Check failed:
> index_of[int](list, item) == some(item) index_of[int](list, item) was
> None[int] some(item) was Some(10) >[FAILED] binary_search
Error: execution of an external program failed:
'/home/u9898287/proj/cdsan/tests/test1 '
Tip: 1 messages have been suppressed, use --verbose to show them.
Error: Execution failed with exit code 1
... Command: "/home/u9898287/.nimble/bin/nim" c --noNimblePath
-d:NimblePkgVersion=0.1.0 "-r" "\-->path:."
"/home/u9898287/proj/cdsan/tests/test1"
The code is a somewhat similar to this piece of java code:
public static int indexOf(int[] a, int key) {
int lo = 0;
int hi = a.length - 1;
while (lo <= hi) {
// Key is in a[lo..hi] or not present.
int mid = lo + (hi - lo) / 2;
if (key < a[mid]) hi = mid - 1;
else if (key > a[mid]) lo = mid + 1;
else return mid;
}
return -1;
}
Run
I can't seem to find the bug in my logic. Any pointers?
