dsearch

Scilab Function
Last update : 11/03/2005

dsearch - binary search (aka dichotomous search in french)

### Calling Sequence

  `[ind, occ, info] = dsearch(X, val [, ch ])`

### Parameters

- `X` : a real vector or matrix
- `val` : a real (row or column) vector with n components in strictly increasing order val(1) < val(2) < ... < val(n)
- `ch` : (optional) a character "c" or "d" (default value "c")
- `ind` : a real vector or matrix with the same dimensions than X
- `occ` : a real vector with the same format than val (but with n-1 components in the case ch="c")
- `info` : integer

### Description

This function is useful to search in an ordered table and/or to count the number of components of a vector falling in some classes (a class being an interval or a value).

By default or when `ch="c"` , this is the interval case, that is, for each X(i) search in which of the n-1 intervals it falls, the intervals being defined by:

                I1 = [val(1), val(2)]
                Ik = (val(k), val(k+1)] for 1 < k <= n-1 ;

and:

  - ind(i) : is the interval number of X(i) (0 if X(i) is not in [val(1),val(n)])
  - occ(k) : is the number of components of X which are in Ik
  - info : is the number of components of X which are not in [val(1),val(n)]

When `ch="d"` case, this is the discrete case, that is, for each X(i) search if it is equal to one val(k) and:

  - ind(i) : is equal to the index of the component of val which matches X(i) (ind(i) = k if X(i)=val(k)) or 0 if X(i) is not in val.
  - occ(k) : is the number of components of X equal to val(k)
  - info : is the number of components of X which are not in the set {val(1),...,val(n)}

### Examples

    // example #1 (elementary stat for U(0,1))
    m = 50000 ; n = 10;
    X = grand(m,1,"def");
    val = linspace(0,1,n+1)';
    [ind, occ] = dsearch(X, val);
    xbasc() ; plot2d2(val, [occ/m;0])  // no normalisation : y must be near 1/n

    // example #2 (elementary stat for B(N,p))
    N = 8 ; p = 0.5; m = 50000;
    X = grand(m,1,"bin",N,p); val = (0:N)';
    [ind, occ] = dsearch(X, val, "d");
    Pexp = occ/m; Pexa = binomial(p,N);
    xbasc() ; hm = 1.1*max(max(Pexa),max(Pexp));
    plot2d3([val val+0.1], [Pexa' Pexp],[1 2],"111",  ...
            "Pexact@Pexp", [-1 0 N+1 hm],[0 N+2 0 6])
    xtitle(  "binomial distribution B("+string(N)+","+string(p)+") :" ...
            +" exact probability versus experimental ones")

    // example #3 (piecewise Hermite polynomial)
    x = [0 ; 0.2 ; 0.35 ; 0.5 ; 0.65 ; 0.8 ;  1];
    y = [0 ; 0.1 ;-0.1  ; 0   ; 0.4  ;-0.1 ;  0];
    d = [1 ; 0   ; 0    ; 1   ; 0    ; 0   ; -1];
    X = linspace(0, 1, 200)';
    ind = dsearch(X, x);
    // define Hermite base functions
    deff("y=Ll(t,k,x)","y=(t-x(k+1))./(x(k)-x(k+1))")   // Lagrange left on Ik
    deff("y=Lr(t,k,x)","y=(t-x(k))./(x(k+1)-x(k))")     // Lagrange right on Ik
    deff("y=Hl(t,k,x)","y=(1-2*(t-x(k))./(x(k)-x(k+1))).*Ll(t,k,x).^2")
    deff("y=Hr(t,k,x)","y=(1-2*(t-x(k+1))./(x(k+1)-x(k))).*Lr(t,k,x).^2")
    deff("y=Kl(t,k,x)","y=(t-x(k)).*Ll(t,k,x).^2")
    deff("y=Kr(t,k,x)","y=(t-x(k+1)).*Lr(t,k,x).^2")
    // plot the curve
    Y = y(ind).*Hl(X,ind) + y(ind+1).*Hr(X,ind) + d(ind).*Kl(X,ind) + d(ind+1).*Kr(X,ind);
    xbasc(); plot2d(X,Y,2) ; plot2d(x,y,-9,"000")
    xtitle("an Hermite piecewise polynomial")
    // NOTE : you can verify by adding these ones :
    // YY = interp(X,x,y,d); plot2d(X,YY,3,"000")

### See Also

`find` , `tabul` ,

### Author

B.P.