binary-search.js 4.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111
  1. /* -*- Mode: js; js-indent-level: 2; -*- */
  2. /*
  3. * Copyright 2011 Mozilla Foundation and contributors
  4. * Licensed under the New BSD license. See LICENSE or:
  5. * http://opensource.org/licenses/BSD-3-Clause
  6. */
  7. exports.GREATEST_LOWER_BOUND = 1;
  8. exports.LEAST_UPPER_BOUND = 2;
  9. /**
  10. * Recursive implementation of binary search.
  11. *
  12. * @param aLow Indices here and lower do not contain the needle.
  13. * @param aHigh Indices here and higher do not contain the needle.
  14. * @param aNeedle The element being searched for.
  15. * @param aHaystack The non-empty array being searched.
  16. * @param aCompare Function which takes two elements and returns -1, 0, or 1.
  17. * @param aBias Either 'binarySearch.GREATEST_LOWER_BOUND' or
  18. * 'binarySearch.LEAST_UPPER_BOUND'. Specifies whether to return the
  19. * closest element that is smaller than or greater than the one we are
  20. * searching for, respectively, if the exact element cannot be found.
  21. */
  22. function recursiveSearch(aLow, aHigh, aNeedle, aHaystack, aCompare, aBias) {
  23. // This function terminates when one of the following is true:
  24. //
  25. // 1. We find the exact element we are looking for.
  26. //
  27. // 2. We did not find the exact element, but we can return the index of
  28. // the next-closest element.
  29. //
  30. // 3. We did not find the exact element, and there is no next-closest
  31. // element than the one we are searching for, so we return -1.
  32. var mid = Math.floor((aHigh - aLow) / 2) + aLow;
  33. var cmp = aCompare(aNeedle, aHaystack[mid], true);
  34. if (cmp === 0) {
  35. // Found the element we are looking for.
  36. return mid;
  37. }
  38. else if (cmp > 0) {
  39. // Our needle is greater than aHaystack[mid].
  40. if (aHigh - mid > 1) {
  41. // The element is in the upper half.
  42. return recursiveSearch(mid, aHigh, aNeedle, aHaystack, aCompare, aBias);
  43. }
  44. // The exact needle element was not found in this haystack. Determine if
  45. // we are in termination case (3) or (2) and return the appropriate thing.
  46. if (aBias == exports.LEAST_UPPER_BOUND) {
  47. return aHigh < aHaystack.length ? aHigh : -1;
  48. } else {
  49. return mid;
  50. }
  51. }
  52. else {
  53. // Our needle is less than aHaystack[mid].
  54. if (mid - aLow > 1) {
  55. // The element is in the lower half.
  56. return recursiveSearch(aLow, mid, aNeedle, aHaystack, aCompare, aBias);
  57. }
  58. // we are in termination case (3) or (2) and return the appropriate thing.
  59. if (aBias == exports.LEAST_UPPER_BOUND) {
  60. return mid;
  61. } else {
  62. return aLow < 0 ? -1 : aLow;
  63. }
  64. }
  65. }
  66. /**
  67. * This is an implementation of binary search which will always try and return
  68. * the index of the closest element if there is no exact hit. This is because
  69. * mappings between original and generated line/col pairs are single points,
  70. * and there is an implicit region between each of them, so a miss just means
  71. * that you aren't on the very start of a region.
  72. *
  73. * @param aNeedle The element you are looking for.
  74. * @param aHaystack The array that is being searched.
  75. * @param aCompare A function which takes the needle and an element in the
  76. * array and returns -1, 0, or 1 depending on whether the needle is less
  77. * than, equal to, or greater than the element, respectively.
  78. * @param aBias Either 'binarySearch.GREATEST_LOWER_BOUND' or
  79. * 'binarySearch.LEAST_UPPER_BOUND'. Specifies whether to return the
  80. * closest element that is smaller than or greater than the one we are
  81. * searching for, respectively, if the exact element cannot be found.
  82. * Defaults to 'binarySearch.GREATEST_LOWER_BOUND'.
  83. */
  84. exports.search = function search(aNeedle, aHaystack, aCompare, aBias) {
  85. if (aHaystack.length === 0) {
  86. return -1;
  87. }
  88. var index = recursiveSearch(-1, aHaystack.length, aNeedle, aHaystack,
  89. aCompare, aBias || exports.GREATEST_LOWER_BOUND);
  90. if (index < 0) {
  91. return -1;
  92. }
  93. // We have found either the exact element, or the next-closest element than
  94. // the one we are searching for. However, there may be more than one such
  95. // element. Make sure we always return the smallest of these.
  96. while (index - 1 >= 0) {
  97. if (aCompare(aHaystack[index], aHaystack[index - 1], true) !== 0) {
  98. break;
  99. }
  100. --index;
  101. }
  102. return index;
  103. };