Changeset 13579


Ignore:
Timestamp:
10/10/12 08:11:42 (12 years ago)
Author:
Eric.Larour
Message:

CHG: had to template the binary_search for doubles, as AD mode compile was not working.

Location:
issm/trunk-jpl/src/c/shared/Sorting
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • issm/trunk-jpl/src/c/shared/Sorting/binary_search.cpp

    r13577 r13579  
    6464        return found;
    6565} /*}}}*/
    66 int binary_search(int* poffset,double target,double* list,int length){ /*{{{*/
    67         /*
    68          *             l[0]  l[1]  l[2]        l[n]  l[n+1]   l[length-1]
    69          *     <-------+-----+-----+-----+ ... +-----+........+-------------->
    70          * offset: -1     0     1     2           n              length -1
    71          * 
    72          *  offset = -1        target < list[0]
    73          *  offset = n         list[n] <= target < list[n+1]
    74          *  offset = length-1  list[length-1] <= target
    75          */
    76 
    77         /*output: */
    78         int offset = 0;
    79         int found  = 0;
    80 
    81         /*intermediary: */
    82         int n0 = 0;
    83         int n1 = int(length/2);
    84         int n2 = length-1;
    85 
    86         if(target<list[n0]){
    87                 found  = 1;
    88                 offset = -1;
    89         }
    90         else if(target>=list[n2]){
    91                 found  = 1;
    92                 offset = length-1;
    93         }
    94         else{
    95                 for(;;){
    96                         /*did we find the target?*/
    97                         if(list[n1]<=target && list[n1+1]>target){
    98                                 found  = 1;
    99                                 offset = n1;
    100                                 break;
    101                         }
    102                         else if(target < list[n1]){
    103                                 n2 = n1;
    104                                 n1 = n0 + int((n2-n0)/2);
    105                         }
    106                         else{
    107                                 n0 = n1;
    108                                 n1 = n0 + int((n2-n0)/2);
    109                         }
    110                 }
    111         }
    112 
    113         /*Assign output pointer and return*/
    114         *poffset=offset;
    115         return found;
    116 } /*}}}*/

  • issm/trunk-jpl/src/c/shared/Sorting/sorting.h

    r13569 r13579  
    77
    88int binary_search(int* poffset,int target,int* sorted_integers,int num_integers);
    9 int binary_search(int* poffset,double target,double* sorted_doubles,int num_doubles);
     9template <typename doubletype> int binary_search(int* poffset,doubletype target,doubletype* list,int length){ /*{{{*/
     10        /*
     11         *             l[0]  l[1]  l[2]        l[n]  l[n+1]   l[length-1]
     12         *     <-------+-----+-----+-----+ ... +-----+........+-------------->
     13         * offset: -1     0     1     2           n              length -1
     14         * 
     15         *  offset = -1        target < list[0]
     16         *  offset = n         list[n] <= target < list[n+1]
     17         *  offset = length-1  list[length-1] <= target
     18         */
     19
     20        /*output: */
     21        int offset = 0;
     22        int found  = 0;
     23
     24        /*intermediary: */
     25        int n0 = 0;
     26        int n1 = int(length/2);
     27        int n2 = length-1;
     28
     29        if(target<list[n0]){
     30                found  = 1;
     31                offset = -1;
     32        }
     33        else if(target>=list[n2]){
     34                found  = 1;
     35                offset = length-1;
     36        }
     37        else{
     38                for(;;){
     39                        /*did we find the target?*/
     40                        if(list[n1]<=target && list[n1+1]>target){
     41                                found  = 1;
     42                                offset = n1;
     43                                break;
     44                        }
     45                        else if(target < list[n1]){
     46                                n2 = n1;
     47                                n1 = n0 + int((n2-n0)/2);
     48                        }
     49                        else{
     50                                n0 = n1;
     51                                n1 = n0 + int((n2-n0)/2);
     52                        }
     53                }
     54        }
     55
     56        /*Assign output pointer and return*/
     57        *poffset=offset;
     58        return found;
     59} /*}}}*/
    1060
    1161#endif //ifndef _SORTING_H_
Note: See TracChangeset for help on using the changeset viewer.