mfbt/BinarySearch.h

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
   3 /* This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 #ifndef mozilla_BinarySearch_h
   8 #define mozilla_BinarySearch_h
   9
  10 #include "mozilla/Assertions.h"
  11
  12 #include <stddef.h>
  13
  14 namespace mozilla {
  15
  16 /*
  17  * The algorithm searches the given container |aContainer| over the sorted
  18  * index range [aBegin, aEnd) for an index |i| where |aContainer[i] == aTarget|.
  19  * If such an index |i| is found, BinarySearch returns |true| and the index is
  20  * returned via the outparam |aMatchOrInsertionPoint|. If no index is found,
  21  * BinarySearch returns |false| and the outparam returns the first index in
  22  * [aBegin, aEnd] where |aTarget| can be inserted to maintain sorted order.
  23  *
  24  * Example:
  25  *
  26  *   Vector<int> sortedInts = ...
  27  *
  28  *   size_t match;
  29  *   if (BinarySearch(sortedInts, 0, sortedInts.length(), 13, &match)) {
  30  *     printf("found 13 at %lu\n", match);
  31  *   }
  32  */
  33
  34 template <typename Container, typename T>
  35 bool
  36 BinarySearch(const Container& aContainer, size_t aBegin, size_t aEnd,
  37              T aTarget, size_t* aMatchOrInsertionPoint)
  38 {
  39   MOZ_ASSERT(aBegin <= aEnd);
  40
  41   size_t low = aBegin;
  42   size_t high = aEnd;
  43   while (low != high) {
  44     size_t middle = low + (high - low) / 2;
  45
  46     // Allow any intermediate type so long as it provides a suitable ordering
  47     // relation.
  48     const auto& middleValue = aContainer[middle];
  49
  50     MOZ_ASSERT(aContainer[low] <= aContainer[middle]);
  51     MOZ_ASSERT(aContainer[middle] <= aContainer[high - 1]);
  52     MOZ_ASSERT(aContainer[low] <= aContainer[high - 1]);
  53
  54     if (aTarget == middleValue) {
  55       *aMatchOrInsertionPoint = middle;
  56       return true;
  57     }
  58
  59     if (aTarget < middleValue) {
  60       high = middle;
  61     } else {
  62       low = middle + 1;
  63     }
  64   }
  65
  66   *aMatchOrInsertionPoint = low;
  67   return false;
  68 }
  69
  70 } // namespace mozilla
  71
  72 #endif // mozilla_BinarySearch_h