• Adnan (39/39) Feb 12 2020 I am debugging my simple binary search (I still am):
• Anonymouse (14/19) Feb 13 2020 It's ulong -1, which is the type idx is of on 64-bit systems. On

Adnan <relay.public.adnan outlook.com> writes:

I am debugging my simple binary search (I still am):

module binary_search;

debug {
     static import std;
}

int indexOf(T)(const T[] list, const T key) {
     ulong lo = 0;
     ulong hi = list.length - 1;
     while (hi > lo) {
         const ulong mid = lo + (hi - lo) / 2;
         if (list[mid] > key)
             hi = mid - 1;
         else if (list[mid] < key)
             lo = mid + 1;
         else {
             std.writeln("----Returning ", mid, "----"); // says 
its returning 0
             return cast(int) mid;
         }
     }
     return -1;
}

unittest {
     scope (success)
         std.writeln("binary_search.indexOf -- ok");

     int[] arr;
     foreach (i; 0 .. 101)
         arr ~= i;
     assert(arr.length > 1);
     foreach (idx, i; arr)
         assert(indexOf(arr, i) == idx);
}


However my test fails saying something like:
source/binary_search.d(33): [unittest] 18446744073709551615 != 1
core.exception.AssertError source/binary_search.d(33): 
18446744073709551615 != 1

What's causing this underflow?

I am using "dflags": ["-checkaction=context"] in my dub 
configuration file.

Anonymouse <zorael gmail.com> writes:

On Thursday, 13 February 2020 at 07:49:13 UTC, Adnan wrote:
 However my test fails saying something like:
 source/binary_search.d(33): [unittest] 18446744073709551615 != 1
 core.exception.AssertError source/binary_search.d(33): 
 18446744073709551615 != 1

 What's causing this underflow?

It's ulong -1, which is the type idx is of on 64-bit systems. On 
32-bit systems it will be uint -1 and say "4294967295 != 0". 
indexOf is probably not doing what you think it's doing.

int indexOf(T)(const T[] list, const T key) {
     return -1;
}

void main()
{
     int[] arr = [ 0 ];
     foreach (idx, i; arr)
         assert(indexOf(arr, i) == idx);  // 18446744073709551615 
!= 0
}