From c0d055366c18b2f3a71435c7c07ce0afe126f85e Mon Sep 17 00:00:00 2001 From: Anthony LaTorre Date: Tue, 6 Sep 2011 23:57:18 -0400 Subject: fix devious assumption in searchsorted that if searching a length one array it assumed the array was meant to be in descending order; it now assumes ascending order and this assumption is documented. --- src/sorting.h | 8 ++++++-- 1 file changed, 6 insertions(+), 2 deletions(-) (limited to 'src/sorting.h') diff --git a/src/sorting.h b/src/sorting.h index 03eabc6..9fd52fe 100644 --- a/src/sorting.h +++ b/src/sorting.h @@ -55,6 +55,10 @@ piksrt2(int n, T *arr, U *brr) } } +/* Returns the index in `arr` where `x` should be inserted in order to + maintain order. If `n` equals one, return the index such that, when + `x` is inserted, `arr` will be in ascending order. +*/ template __device__ unsigned long searchsorted(unsigned long n, T *arr, const T &x) @@ -65,12 +69,12 @@ searchsorted(unsigned long n, T *arr, const T &x) jl = 0; ju = n; - ascnd = (arr[n-1] > arr[0]); + ascnd = (arr[n-1] >= arr[0]); while (ju-jl > 1) { jm = (ju+jl) >> 1; - if (x >= arr[jm] == ascnd) + if ((x > arr[jm]) == ascnd) jl = jm; else ju = jm; -- cgit