1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/mfbt/BinarySearch.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,66 @@
1.4 +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
1.5 +/* vim: set ts=8 sts=2 et sw=2 tw=80: */
1.6 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.7 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.8 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.9 +
1.10 +#ifndef mozilla_BinarySearch_h
1.11 +#define mozilla_BinarySearch_h
1.12 +
1.13 +#include "mozilla/Assertions.h"
1.14 +
1.15 +#include <stddef.h>
1.16 +
1.17 +namespace mozilla {
1.18 +
1.19 +/*
1.20 + * The algorithm searches the given container 'c' over the sorted index range
1.21 + * [begin, end) for an index 'i' where 'c[i] == target'. If such an index 'i' is
1.22 + * found, BinarySearch returns 'true' and the index is returned via the outparam
1.23 + * 'matchOrInsertionPoint'. If no index is found, BinarySearch returns 'false'
1.24 + * and the outparam returns the first index in [begin, end] where 'target' can
1.25 + * be inserted to maintain sorted order.
1.26 + *
1.27 + * Example:
1.28 + *
1.29 + * Vector<int> sortedInts = ...
1.30 + *
1.31 + * size_t match;
1.32 + * if (BinarySearch(sortedInts, 0, sortedInts.length(), 13, &match))
1.33 + * printf("found 13 at %lu\n", match);
1.34 + */
1.35 +
1.36 +template <typename Container, typename T>
1.37 +bool
1.38 +BinarySearch(const Container &c, size_t begin, size_t end, T target, size_t *matchOrInsertionPoint)
1.39 +{
1.40 + MOZ_ASSERT(begin <= end);
1.41 +
1.42 + size_t low = begin;
1.43 + size_t high = end;
1.44 + while (low != high) {
1.45 + size_t middle = low + (high - low) / 2;
1.46 + const T &middleValue = c[middle];
1.47 +
1.48 + MOZ_ASSERT(c[low] <= c[middle]);
1.49 + MOZ_ASSERT(c[middle] <= c[high - 1]);
1.50 + MOZ_ASSERT(c[low] <= c[high - 1]);
1.51 +
1.52 + if (target == middleValue) {
1.53 + *matchOrInsertionPoint = middle;
1.54 + return true;
1.55 + }
1.56 +
1.57 + if (target < middleValue)
1.58 + high = middle;
1.59 + else
1.60 + low = middle + 1;
1.61 + }
1.62 +
1.63 + *matchOrInsertionPoint = low;
1.64 + return false;
1.65 +}
1.66 +
1.67 +} // namespace mozilla
1.68 +
1.69 +#endif // mozilla_BinarySearch_h
