Changeset 13579
- Timestamp:
- 10/10/12 08:11:42 (12 years ago)
- 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 64 64 return found; 65 65 } /*}}}*/ 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 -171 *72 * offset = -1 target < list[0]73 * offset = n list[n] <= target < list[n+1]74 * offset = length-1 list[length-1] <= target75 */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 7 7 8 8 int 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); 9 template <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 } /*}}}*/ 10 60 11 61 #endif //ifndef _SORTING_H_
Note:
See TracChangeset
for help on using the changeset viewer.