28fd2116ab4e1e6aa7d5b39f7c8994c38a6ad674
[scilab.git] / scilab / modules / elementary_functions / help / en_US / searchandsort / dsearch.xml
1 <?xml version="1.0" encoding="utf-8"?>
2 <!--
3  * Scilab ( http://www.scilab.org/ ) - This file is part of Scilab
4  * Copyright (C) Bruno Pincon
5  * Copyright (C) 2011 - DIGITEO - Michael Baudin
6  * 
7  * This file must be used under the terms of the CeCILL.
8  * This source file is licensed as described in the file COPYING, which
9  * you should have received as part of this distribution.  The terms
10  * are also available at    
11  * http://www.cecill.info/licences/Licence_CeCILL_V2-en.txt
12  *
13  -->
14 <refentry xmlns="http://docbook.org/ns/docbook" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:svg="http://www.w3.org/2000/svg" xmlns:ns5="http://www.w3.org/1999/xhtml" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:db="http://docbook.org/ns/docbook" version="5.0-subset Scilab" xml:id="dsearch" xml:lang="en">
15     <refnamediv>
16         <refname>dsearch</refname>
17         <refpurpose>
18             search in ordered sets
19         </refpurpose>
20     </refnamediv>
21     <refsynopsisdiv>
22         <title>Calling Sequence</title>
23         <synopsis>
24             [ind, occ, info] = dsearch(X, s )
25             [ind, occ, info] = dsearch(X, s , ch )
26         </synopsis>
27     </refsynopsisdiv>
28     <refsection>
29         <title>Arguments</title>
30         <variablelist>
31             <varlistentry>
32                 <term>X</term>
33                 <listitem>
34                     <para>
35                         a mx-by-nx matrix of doubles, the entries to locate.
36                     </para>
37                 </listitem>
38             </varlistentry>
39             <varlistentry>
40                 <term>s</term>
41                 <listitem>
42                     <para>
43                         a n-by-1 or 1-by-n matrix of doubles, the 
44                         intervals (if ch="c") or the set (if ch="d"). 
45                         The values in s must be in strictly increasing order:
46                         s(1) &lt; s(2) &lt; ... &lt; s(n)
47                     </para>
48                 </listitem>
49             </varlistentry>
50             <varlistentry>
51                 <term>ch</term>
52                 <listitem>
53                     <para>
54                         a 1-by-1 matrix of strings, the type of search (default ch="c").
55                         Available values are ch="c" or ch="d".
56                     </para>
57                 </listitem>
58             </varlistentry>
59             <varlistentry>
60                 <term>ind</term>
61                 <listitem>
62                     <para>
63                         a mx-by-nx matrix of doubles. 
64                         The location of the X values in the intervals or the set defined by <literal>s</literal>.
65                     </para>
66                 </listitem>
67             </varlistentry>
68             <varlistentry>
69                 <term>occ</term>
70                 <listitem>
71                     <para>
72                         If ch="c", a (n-1)-by-1 or 1-by-(n-1) of doubles. 
73                         If ch="d", a n-by-1 or 1-by-n of doubles. The number of entries 
74                         from X in the intervals s.
75                     </para>
76                 </listitem>
77             </varlistentry>
78             <varlistentry>
79                 <term>info</term>
80                 <listitem>
81                     <para>
82                         a 1-by-1 matrix of doubles. The number of X entries which are not in <literal>s</literal>.
83                     </para>
84                 </listitem>
85             </varlistentry>
86         </variablelist>
87     </refsection>
88     <refsection>
89         <title>Description</title>
90         <para>
91             This function locates the indices of the entries in X in the intervals or the set defined by s.
92         </para>
93         <para>
94             If <literal>ch="c"</literal> (default), we consider the
95             intervals <literal>I1 = [s(1), s(2)]</literal> 
96             and <literal>Ik = (s(k), s(k+1)]</literal> for <literal>k=2,...,n-1</literal>. 
97             Notice that the bounds of <literal>I1</literal> are closed, 
98             while the left bounds of <literal>I2</literal>, ..., <literal>In</literal> are 
99             opened.
100             For each entry <literal>X(i)</literal>, 
101             we search the interval <literal>Ik</literal> which contains X(i), i.e. we search k such 
102             that <literal>s(k)&lt;X(i)&lt;=s(k+1)</literal>.
103         </para>
104         <para>
105             More precisely,
106         </para>
107         <variablelist>
108             <varlistentry>
109                 <term>ind(i)</term>
110                 <listitem>
111                     <para>
112                         is k such that <literal>Ik</literal> contains X(i) or 
113                         0 if X(i) is not in any interval <literal>Ik</literal>.
114                     </para>
115                 </listitem>
116             </varlistentry>
117             <varlistentry>
118                 <term>occ(k)</term>
119                 <listitem>
120                     <para>
121                         is the number of components of <literal>X</literal> which are in <literal>Ik</literal>
122                     </para>
123                 </listitem>
124             </varlistentry>
125             <varlistentry>
126                 <term>info</term>
127                 <listitem>
128                     <para>
129                         is the number of components of <literal>X</literal> which are not in
130                         any interval <literal>Ik</literal>.
131                     </para>
132                 </listitem>
133             </varlistentry>
134         </variablelist>
135         <para>
136             If <literal>ch="d"</literal>, we consider the set {s(1),s(2),...,s(n)}.
137             For each X(i), search k such that X(i)=s(k).
138         </para>
139         <para>
140             More precisely, 
141         </para>
142         <variablelist>
143             <varlistentry>
144                 <term>ind(i)</term>
145                 <listitem>
146                     <para>
147                         is k if X(i)=s(k) or 0 if X(i) is not in s.
148                     </para>
149                 </listitem>
150             </varlistentry>
151             <varlistentry>
152                 <term>occ(k)</term>
153                 <listitem>
154                     <para>
155                         is the number of entries in X equal to s(k)
156                     </para>
157                 </listitem>
158             </varlistentry>
159             <varlistentry>
160                 <term>info</term>
161                 <listitem>
162                     <para>
163                         is the number of entries in X which are not in the set
164                         {s(1),...,s(n)}.
165                     </para>
166                 </listitem>
167             </varlistentry>
168         </variablelist>
169         <para>
170             The ch="c" option can be used to compute the empirical histogram of a function given a dataset.
171             The ch="d" option can be used to compute the entries in X which are present in the set s.
172         </para>
173     </refsection>
174     <refsection>
175         <title>Examples</title>
176         <para>
177             In the following example, we consider 3 intervals <literal>I1=[5,11]</literal>, 
178             <literal>I2=(11,15]</literal> and <literal>I3=(15,20]</literal>.
179             We are looking for the location of the entries of <literal>X=[11 13 1 7 5 2 9]</literal> 
180             in these intervals.
181         </para>
182         <programlisting role="example"><![CDATA[ 
183 [ind, occ, info] = dsearch([11 13 1 7 5 2 9], [5 11 15 20])
184     ]]></programlisting>
185         <para>
186             The previous example produces the following output.
187         </para>
188         <screen><![CDATA[ 
189 -->[ind, occ, info] = dsearch([11 13 1 7 5 2 9], [5 11 15 20])
190  info  =
191     2.
192  occ  =
193     4.    1.    0.
194  ind  =
195     1.    2.    0.    1.    1.    0.    1.
196     ]]></screen>
197         <para>
198             We now explain these results.
199         </para>
200         <itemizedlist>
201             <listitem>
202                 <para>X(1)=11 is in the interval I1, hence ind(1)=1.</para>
203             </listitem>
204             <listitem>
205                 <para> X(2)=13 is in the interval I2, hence ind(2)=2.</para>
206             </listitem>
207             <listitem>
208                 <para> X(3)=1 is not in any interval, hence ind(3)=0.</para>
209             </listitem>
210             <listitem>
211                 <para> X(4)=7 is in the interval I1, hence ind(4)=1.</para>
212             </listitem>
213             <listitem>
214                 <para> X(5)=5 is in the interval I1, hence ind(5)=1.</para>
215             </listitem>
216             <listitem>
217                 <para> X(6)=2 is not in any interval, hence ind(6)=0.</para>
218             </listitem>
219             <listitem>
220                 <para> X(7)=9 is in the interval I1, hence ind(7)=1.</para>
221             </listitem>
222             <listitem>
223                 <para> There are four X entries (5, 7, 9 and 11) in I1, hence occ(1)=4.</para>
224             </listitem>
225             <listitem>
226                 <para> There is one X entry (i.e. 13) in I2, hence occ(2)=1.</para>
227             </listitem>
228             <listitem>
229                 <para> There is no X entry in I3, hence occ(3)=0.</para>
230             </listitem>
231             <listitem>
232                 <para> There are two X entries (i.e. 1, 2) which are not in any interval, hence info=2.</para>
233             </listitem>
234         </itemizedlist>
235         <para>
236             In the following example, we consider the set [5 11 15 20] and 
237             are searching the location of the X entries in this set.
238         </para>
239         <programlisting role="example"><![CDATA[ 
240 [ind, occ, info] = dsearch([11 13 1 7 5 2 9], [5 11 15 20],"d" )
241     ]]></programlisting>
242         <para>
243             The previous example produces the following output.
244         </para>
245         <screen><![CDATA[ 
246 -->[ind, occ, info] = dsearch([11 13 1 7 5 2 9], [5 11 15 20],"d" )
247  info  =
248     5.
249  occ  =
250     1.    1.    0.    0.
251  ind  =
252     2.    0.    0.    0.    1.    0.    0.
253     ]]></screen>
254         <para>
255             The following is a detailed explanation for the previous results.
256         </para>
257         <itemizedlist>
258             <listitem>
259                 <para>
260                     X(1)=11 is in the set <literal>s</literal> at position #2, hence ind(1)=2.
261                 </para>
262             </listitem>
263             <listitem>
264                 <para>
265                     X(2)=13 is not in the set <literal>s</literal>, hence ind(2)=0.
266                 </para>
267             </listitem>
268             <listitem>
269                 <para>
270                     X(3)=1 is not in the set <literal>s</literal>, hence ind(3)=0.
271                 </para>
272             </listitem>
273             <listitem>
274                 <para>
275                     X(4)=7 is not in the set <literal>s</literal>, hence ind(4)=0.
276                 </para>
277             </listitem>
278             <listitem>
279                 <para>
280                     X(5)=5 is in the set <literal>s</literal> at position #1, hence ind(5)=1.
281                 </para>
282             </listitem>
283             <listitem>
284                 <para>
285                     X(6)=2 is not in the set <literal>s</literal>, hence ind(6)=0.
286                 </para>
287             </listitem>
288             <listitem>
289                 <para>
290                     X(7)=9 is not in the set <literal>s</literal>, hence ind(7)=0.
291                 </para>
292             </listitem>
293             <listitem>
294                 <para>
295                     There is one entry X (i.e. 5) equal to 5, hence occ(1)=1.
296                 </para>
297             </listitem>
298             <listitem>
299                 <para>
300                     There is one entry X (i.e. 11) equal to 1, hence occ(2)=1.
301                 </para>
302             </listitem>
303             <listitem>
304                 <para>
305                     There are no entries matching <literal>s(3)</literal>, hence occ(3)=0.
306                 </para>
307             </listitem>
308             <listitem>
309                 <para>
310                     There are no entries matching <literal>s(4)</literal>, hence occ(4)=0.
311                 </para>
312             </listitem>
313             <listitem>
314                 <para>
315                     There are five X entries (i.e. 13, 1, 7, 2, 9) which are not in the set <literal>s</literal>, hence info=5.
316                 </para>
317             </listitem>
318         </itemizedlist>
319         <para>
320             The values in <literal>s</literal> must be in increasing order, whatever the 
321             value of the <literal>ch</literal> option. 
322             If this is not true, an error is generated, as in the following session.
323         </para>
324         <screen><![CDATA[ 
325 -->dsearch([11 13 1 7 5 2 9], [2 1])
326 !--error 999
327 dsearch   : the array s (arg 2) is not well ordered
328 -->dsearch([11 13 1 7 5 2 9], [2 1],"d")
329 !--error 999
330 dsearch   : the array s (arg 2) is not well ordered
331     ]]></screen>
332     </refsection>
333     <refsection>
334         <title>Advanced Examples</title>
335         <para>
336             In the following example, we compare the empirical histogram of uniform
337             random numbers in [0,1) with the uniform distribution function.
338             To perform this comparison, we use the default search algorithm based on 
339             intervals (ch="c").
340             We generate X as a collection of m=50 000 uniform random numbers in
341             the range [0,1).
342             We consider the n=10 values equally equally spaced values in the [0,1] range and
343             consider the associated intervals.
344             Then we count the number of entries in X which fall in the intervals:
345             this is the empirical histogram of the uniform distribution function.
346             The expectation for occ/m is equal to 1/(n-1).
347         </para>
348         <programlisting role="example"><![CDATA[ 
349 m = 50000 ; 
350 n = 10;
351 X = grand(m,1,"def");
352 s = linspace(0,1,n)';
353 [ind, occ] = dsearch(X, s);
354 e = 1/(n-1)*ones(1,n-1);
355 scf() ; 
356 plot(s(1:n-1), occ/m,"bo");
357 plot(s(1:n-1), e,"r-");
358 legend(["Experiment","Expectation"]);
359 xtitle("Uniform random numbers","X","P(X)");
360  ]]></programlisting>
361         <para>
362             In the following example, we compare the histogram of binomially distributed
363             random numbers with the binomial probability distribution function B(N,p),
364             with N=8 and p=0.5.
365             To perform this comparison, we use the discrete search algorithm based on
366             a set (ch="d").
367         </para>
368         <programlisting role="example"><![CDATA[ 
369 N = 8 ; 
370 p = 0.5; 
371 m = 50000;
372 X = grand(m,1,"bin",N,p); 
373 s = (0:N)';
374 [ind, occ] = dsearch(X, s, "d");
375 Pexp = occ/m; 
376 Pexa = binomial(p,N);
377 scf() ; 
378 plot(s,Pexp,"bo");
379 plot(s,Pexa',"r-");
380 xtitle("Binomial distribution B(8,0.5)","X","P(X)");
381 legend(["Experiment","Expectation"]);
382 ]]></programlisting>
383         <para>
384             In the following example, we use piecewise Hermite polynomials to 
385             interpolate a dataset.
386         </para>
387         <programlisting role="example"><![CDATA[ 
388
389       // define Hermite base functions
390       function y=Ll(t,k,x)
391         // Lagrange left on Ik
392         y=(t-x(k+1))./(x(k)-x(k+1))
393       endfunction
394       function y=Lr(t,k,x)
395         // Lagrange right on Ik
396         y=(t-x(k))./(x(k+1)-x(k))
397       endfunction
398       function y=Hl(t,k,x)
399         y=(1-2*(t-x(k))./(x(k)-x(k+1))).*Ll(t,k,x).^2
400       endfunction
401       function y=Hr(t,k,x)
402         y=(1-2*(t-x(k+1))./(x(k+1)-x(k))).*Lr(t,k,x).^2
403       endfunction
404       function y=Kl(t,k,x)
405         y=(t-x(k)).*Ll(t,k,x).^2
406       endfunction
407       function y=Kr(t,k,x)
408         y=(t-x(k+1)).*Lr(t,k,x).^2
409       endfunction
410
411       x = [0 ; 0.2 ; 0.35 ; 0.5 ; 0.65 ; 0.8 ;  1];
412       y = [0 ; 0.1 ;-0.1  ; 0   ; 0.4  ;-0.1 ;  0];
413       d = [1 ; 0   ; 0    ; 1   ; 0    ; 0   ; -1];
414       X = linspace(0, 1, 200)';
415       ind = dsearch(X, x);
416
417       // plot the curve
418       Y = y(ind).*Hl(X,ind) + y(ind+1).*Hr(X,ind) + d(ind).*Kl(X,ind) + d(ind+1).*Kr(X,ind);
419       scf();
420       plot(X,Y,"k-");
421       plot(x,y,"bo")
422       xtitle("Hermite piecewise polynomial");
423       legend(["Polynomial","Data"]);
424       // NOTE : you can verify by adding these ones :
425       // YY = interp(X,x,y,d); plot2d(X,YY,3,"000")
426       ]]></programlisting>
427     </refsection>
428     <refsection role="see also">
429         <title>See Also</title>
430         <simplelist type="inline">
431             <member>
432                 <link linkend="find">find</link>
433             </member>
434             <member>
435                 <link linkend="tabul">tabul</link>
436             </member>
437         </simplelist>
438     </refsection>
439 </refentry>