Mercurial > hg > camir-aes2014
annotate toolboxes/distance_learning/mlr/util/binarysearch.c @ 0:e9a9cd732c1e tip
first hg version after svn
| author | wolffd |
|---|---|
| date | Tue, 10 Feb 2015 15:05:51 +0000 |
| parents | |
| children |
| rev | line source |
|---|---|
| wolffd@0 | 1 /* CREATED:2010-01-17 08:12:57 by Brian McFee <bmcfee@cs.ucsd.edu> */ |
| wolffd@0 | 2 /* binarysearch.c |
| wolffd@0 | 3 * |
| wolffd@0 | 4 * binary search |
| wolffd@0 | 5 * |
| wolffd@0 | 6 * Compile: |
| wolffd@0 | 7 * mex binarysearch.c |
| wolffd@0 | 8 */ |
| wolffd@0 | 9 |
| wolffd@0 | 10 #include "mex.h" |
| wolffd@0 | 11 |
| wolffd@0 | 12 |
| wolffd@0 | 13 void mexFunction(int nlhs, mxArray *plhs[], int nrhs, const mxArray *prhs[]) |
| wolffd@0 | 14 { |
| wolffd@0 | 15 /* Declare variables */ |
| wolffd@0 | 16 int nQuery, nData; /* number of elements */ |
| wolffd@0 | 17 double *pQuery, *pData; /* input arrays */ |
| wolffd@0 | 18 double *positions; /* output array(s) */ |
| wolffd@0 | 19 |
| wolffd@0 | 20 int i; |
| wolffd@0 | 21 |
| wolffd@0 | 22 if (nrhs != 2) { |
| wolffd@0 | 23 mexErrMsgTxt("Two input arguments are required."); |
| wolffd@0 | 24 } |
| wolffd@0 | 25 if (nlhs > 1) { |
| wolffd@0 | 26 mexErrMsgTxt("Too many output arguments."); |
| wolffd@0 | 27 } |
| wolffd@0 | 28 |
| wolffd@0 | 29 if (!(mxIsDouble(prhs[0])) || !(mxIsDouble(prhs[1]))) { |
| wolffd@0 | 30 mexErrMsgTxt("Input arrays must be of type double."); |
| wolffd@0 | 31 } |
| wolffd@0 | 32 |
| wolffd@0 | 33 nQuery = mxGetNumberOfElements(prhs[0]); |
| wolffd@0 | 34 nData = mxGetNumberOfElements(prhs[1]); |
| wolffd@0 | 35 pQuery = (double *)mxGetPr(prhs[0]); |
| wolffd@0 | 36 pData = (double *)mxGetPr(prhs[1]); |
| wolffd@0 | 37 |
| wolffd@0 | 38 plhs[0] = mxCreateDoubleMatrix(1, nQuery, mxREAL); |
| wolffd@0 | 39 positions = mxGetPr(plhs[0]); |
| wolffd@0 | 40 |
| wolffd@0 | 41 /* Now for the meat */ |
| wolffd@0 | 42 |
| wolffd@0 | 43 for (i = 0; i < nQuery; i++) { |
| wolffd@0 | 44 positions[i] = 0; |
| wolffd@0 | 45 positions[i] = binarysearch(pQuery[i], pData, nData); |
| wolffd@0 | 46 } |
| wolffd@0 | 47 |
| wolffd@0 | 48 mxSetN(plhs[0], nQuery); |
| wolffd@0 | 49 } |
| wolffd@0 | 50 |
| wolffd@0 | 51 int binarysearch(double q, double *data, int n) { |
| wolffd@0 | 52 int l = 0; |
| wolffd@0 | 53 int u = n-1; |
| wolffd@0 | 54 int pivot; |
| wolffd@0 | 55 |
| wolffd@0 | 56 while (l < u) { |
| wolffd@0 | 57 pivot = l + (u - l) / 2; |
| wolffd@0 | 58 |
| wolffd@0 | 59 if (q > data[pivot]) { |
| wolffd@0 | 60 u = pivot - 1; |
| wolffd@0 | 61 } else { |
| wolffd@0 | 62 l = pivot + 1; |
| wolffd@0 | 63 } |
| wolffd@0 | 64 } |
| wolffd@0 | 65 |
| wolffd@0 | 66 /* Break ties to the right */ |
| wolffd@0 | 67 if (l == n || q > data[l]) { |
| wolffd@0 | 68 return l; |
| wolffd@0 | 69 } else { |
| wolffd@0 | 70 return l + 1; |
| wolffd@0 | 71 } |
| wolffd@0 | 72 |
| wolffd@0 | 73 } |