Changeset 13575
- Timestamp:
- 10/09/12 21:06:07 (12 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
issm/trunk-jpl/src/c/shared/Sorting/binary_search.cpp
r13572 r13575 64 64 return found; 65 65 } /*}}}*/ 66 int binary_search(int* poffset,double target,double* sorted_doubles,int num_doubles){ /*{{{*/66 int binary_search(int* poffset,double target,double* list,int num_doubles){ /*{{{*/ 67 67 68 68 /*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 */ 74 75 75 76 /*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; 79 80 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; 86 83 offset = -1; 87 found = 0;88 84 } 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; 96 88 } 97 89 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; 103 96 } 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); 107 104 } 108 105 } 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; 122 109 } 123 110
Note:
See TracChangeset
for help on using the changeset viewer.