Changeset 13577 for issm/trunk-jpl/src/c/shared

Timestamp:

10/10/12 07:39:19 (13 years ago)

Author:

Mathieu Morlighem

Message:

CHG: even simpler binary_search for doubles: return segment number

File:

• issm/trunk-jpl/src/c/shared/Sorting/binary_search.cpp (modified) (2 diffs)

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

@@ -64 +64 @@
         return found;
 } /*}}}*/
-int binary_search(int* poffset,double target,double* list,int num_doubles){ /*{{{*/
+int binary_search(int* poffset,double target,double* list,int length){ /*{{{*/
+        /*
+         *             l[0]  l[1]  l[2]        l[n]  l[n+1]   l[length-1]
+         *     <-------+-----+-----+-----+ ... +-----+........+-------------->
+         * offset: -1     0     1     2           n              length -1
+         *  
+         *  offset = -1        target < list[0]
+         *  offset = n         list[n] <= target < list[n+1]
+         *  offset = length-1  list[length-1] <= target
+         */
 
         /*output: */
         int offset = 0;
-        int found  = 0; /*found =  0: not found.
-                                                        found = -1: found, and target is < first element
-                                                        found =  1: found, and target is == to value at offset 
-                                                        found =  2: found, and target is > to value at offset  and < to value at offset+1
-                                                        found =  3: found, and target is >= last value */
+        int found  = 0;
 
         /*intermediary: */
         int n0 = 0;
-        int n1 = int(num_doubles/2);
-        int n2 = num_doubles-1;
+        int n1 = int(length/2);
+        int n2 = length-1;
 
         if(target<list[n0]){
-                found  = -1;
+                found  = 1;
                 offset = -1;
         }
         else if(target>=list[n2]){
-                found  = 3;
-                offset = n2-1;
+                found  = 1;
+                offset = length-1;
         }
         else{
-                while(!found){
+                for(;;){
                         /*did we find the target?*/
                         if(list[n1]<=target && list[n1+1]>target){
-                                found = 1;
+                                found  = 1;
                                 offset = n1;
                                 break;
                         }
-                        if(target < list[n1]){
+                        else if(target < list[n1]){
                                 n2 = n1;
                                 n1 = n0 + int((n2-n0)/2);
@@ -104 +109 @@
                         }
                 }
-
-                //did we find an exact target?
-                if(list[n1]==target) found = 2;
         }
 
-        /*Assign output pointers:*/
+        /*Assign output pointer and return*/
         *poffset=offset;
-        
-        /*Return result: */
         return found;
 } /*}}}*/