Changeset 13575


Ignore:
Timestamp:
10/09/12 21:06:07 (12 years ago)
Author:
Mathieu Morlighem
Message:

BUG: rewrote binary_search for double, there was a segfault in the previous implementation

File:
1 edited

Legend:

Unmodified
Added
Removed

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

    r13572 r13575  
    6464        return found;
    6565} /*}}}*/
    66 int binary_search(int* poffset,double target,double* sorted_doubles,int num_doubles){ /*{{{*/
     66int binary_search(int* poffset,double target,double* list,int num_doubles){ /*{{{*/
    6767
    6868        /*output: */
    69         int offset=0; 
    70         int found=0; /*found=0: not found.   
    71                                                 found=1: found, and target is == to value at offset
    72                                                 found=2: found, and target is > to value at offset  and < to value at offset+1
    73                                                 */
     69        int offset = 0;
     70        int found  = 0; /*found =  0: not found.
     71                                                        found = -1: found, and target is < first element
     72                                                        found =  1: found, and target is == to value at offset
     73                                                        found =  2: found, and target is > to value at offset  and < to value at offset+1
     74                                                        found =  3: found, and target is >= last value */
    7475
    7576        /*intermediary: */
    76         double *beg = NULL;
    77         double *end = NULL;
    78         double *mid = NULL;
     77        int n0 = 0;
     78        int n1 = int(num_doubles/2);
     79        int n2 = num_doubles-1;
    7980
    80         // point to beginning and end of the array
    81         beg = sorted_doubles;
    82         end = sorted_doubles+num_doubles;
    83         mid = beg+(int)(num_doubles/2.0);
    84 
    85         if (target<*beg){
     81        if(target<list[n0]){
     82                found  = -1;
    8683                offset = -1;
    87                 found  = 0;
    8884        }
    89         if (*beg==target){
    90                 found  = 1;
    91                 offset = 0;
    92         }
    93         else if(*(end-1)==target){
    94                 found  = 1;
    95                 offset = num_doubles-1;
     85        else if(target>=list[n2]){
     86                found  = 3;
     87                offset = n2-1;
    9688        }
    9789        else{
    98                 while((beg <= end) && !( target>=*mid && target<*(mid+1)) ){
    99                         // is the target in lower or upper half?
    100                         if (target < *mid) {
    101                                 end = mid - 1;  //new end
    102                                 mid = beg + (end-beg)/2;  //new middle
     90                while(!found){
     91                        /*did we find the target?*/
     92                        if(list[n1]<=target && list[n1+1]>target){
     93                                found = 1;
     94                                offset = n1;
     95                                break;
    10396                        }
    104                         else {
    105                                 beg = mid + 1;  //new beginning
    106                                 mid = beg + (end-beg)/2;  //new middle
     97                        if(target < list[n1]){
     98                                n2 = n1;
     99                                n1 = n0 + int((n2-n0)/2);
     100                        }
     101                        else{
     102                                n0 = n1;
     103                                n1 = n0 + int((n2-n0)/2);
    107104                        }
    108105                }
    109                          
    110                 //did we find the target?
    111                 if( target>*mid &&  target<*(mid+1)){
    112                         found=2;
    113                         offset=mid-sorted_doubles;
    114                 }
    115                 else if( target==*mid){
    116                         found=1;
    117                         offset=mid-sorted_doubles;
    118                 }
    119                 else {
    120                         found=0;
    121                 }
     106
     107                //did we find an exact target?
     108                if(list[n1]==target) found = 2;
    122109        }
    123110
Note: See TracChangeset for help on using the changeset viewer.