123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111 |
- exports.GREATEST_LOWER_BOUND = 1;
- exports.LEAST_UPPER_BOUND = 2;
- function recursiveSearch(aLow, aHigh, aNeedle, aHaystack, aCompare, aBias) {
-
-
-
-
-
-
-
-
-
- var mid = Math.floor((aHigh - aLow) / 2) + aLow;
- var cmp = aCompare(aNeedle, aHaystack[mid], true);
- if (cmp === 0) {
-
- return mid;
- }
- else if (cmp > 0) {
-
- if (aHigh - mid > 1) {
-
- return recursiveSearch(mid, aHigh, aNeedle, aHaystack, aCompare, aBias);
- }
-
-
- if (aBias == exports.LEAST_UPPER_BOUND) {
- return aHigh < aHaystack.length ? aHigh : -1;
- } else {
- return mid;
- }
- }
- else {
-
- if (mid - aLow > 1) {
-
- return recursiveSearch(aLow, mid, aNeedle, aHaystack, aCompare, aBias);
- }
-
- if (aBias == exports.LEAST_UPPER_BOUND) {
- return mid;
- } else {
- return aLow < 0 ? -1 : aLow;
- }
- }
- }
- exports.search = function search(aNeedle, aHaystack, aCompare, aBias) {
- if (aHaystack.length === 0) {
- return -1;
- }
- var index = recursiveSearch(-1, aHaystack.length, aNeedle, aHaystack,
- aCompare, aBias || exports.GREATEST_LOWER_BOUND);
- if (index < 0) {
- return -1;
- }
-
-
-
- while (index - 1 >= 0) {
- if (aCompare(aHaystack[index], aHaystack[index - 1], true) !== 0) {
- break;
- }
- --index;
- }
- return index;
- };
|