* Recursive implementation of binary search. * * @param aLow Indices here and lower do not contain the needle. * @param aHigh Indices here and higher do not contain the needle. * @param aNeedle The element being searched for. * @param aHaystack The non-empty array being searched. * @param aCom
(aLow, aHigh, aNeedle, aHaystack, aCompare, aBias)
| 27 | * searching for, respectively, if the exact element cannot be found. |
| 28 | */ |
| 29 | function recursiveSearch(aLow, aHigh, aNeedle, aHaystack, aCompare, aBias) { |
| 30 | // This function terminates when one of the following is true: |
| 31 | // |
| 32 | // 1. We find the exact element we are looking for. |
| 33 | // |
| 34 | // 2. We did not find the exact element, but we can return the index of |
| 35 | // the next-closest element. |
| 36 | // |
| 37 | // 3. We did not find the exact element, and there is no next-closest |
| 38 | // element than the one we are searching for, so we return -1. |
| 39 | var mid = Math.floor((aHigh - aLow) / 2) + aLow; |
| 40 | var cmp = aCompare(aNeedle, aHaystack[mid], true); |
| 41 | if (cmp === 0) { |
| 42 | // Found the element we are looking for. |
| 43 | return mid; |
| 44 | } |
| 45 | else if (cmp > 0) { |
| 46 | // Our needle is greater than aHaystack[mid]. |
| 47 | if (aHigh - mid > 1) { |
| 48 | // The element is in the upper half. |
| 49 | return recursiveSearch(mid, aHigh, aNeedle, aHaystack, aCompare, aBias); |
| 50 | } |
| 51 | |
| 52 | // The exact needle element was not found in this haystack. Determine if |
| 53 | // we are in termination case (3) or (2) and return the appropriate thing. |
| 54 | if (aBias == LEAST_UPPER_BOUND) { |
| 55 | return aHigh < aHaystack.length ? aHigh : -1; |
| 56 | } else { |
| 57 | return mid; |
| 58 | } |
| 59 | } |
| 60 | else { |
| 61 | // Our needle is less than aHaystack[mid]. |
| 62 | if (mid - aLow > 1) { |
| 63 | // The element is in the lower half. |
| 64 | return recursiveSearch(aLow, mid, aNeedle, aHaystack, aCompare, aBias); |
| 65 | } |
| 66 | |
| 67 | // we are in termination case (3) or (2) and return the appropriate thing. |
| 68 | if (aBias == LEAST_UPPER_BOUND) { |
| 69 | return mid; |
| 70 | } else { |
| 71 | return aLow < 0 ? -1 : aLow; |
| 72 | } |
| 73 | } |
| 74 | } |
| 75 | |
| 76 | /** |
| 77 | * This is an implementation of binary search which will always try and return |