Commit 447dc2bb90

Yuri Pieters <magejohnyjtp@gmail.com>
2020-04-09 02:49:42
sort.binarySearch: fix integer underflow (#4980)
When the key was smaller than any value in the array, an error was ocurring with the mid being zero and having 1 subtracted from it.
master
1 parent c45ba49
Changed files (1)
lib
std
sort.zig
lib/std/sort.zig
@@ -10,16 +10,16 @@ pub fn binarySearch(comptime T: type, key: T, items: []const T, comptime compare
         return null;
 
     var left: usize = 0;
-    var right: usize = items.len - 1;
+    var right: usize = items.len;
 
-    while (left <= right) {
+    while (left < right) {
         // Avoid overflowing in the midpoint calculation
         const mid = left + (right - left) / 2;
         // Compare the key with the midpoint element
         switch (compareFn(key, items[mid])) {
             .eq => return mid,
             .gt => left = mid + 1,
-            .lt => right = mid - 1,
+            .lt => right = mid,
         }
     }