The Tor Browser / file comparison
comparison: mfbt/BinarySearch.h
mfbt/BinarySearch.h
- changeset 2
- 7e26c7da4463
equal
deleted
inserted
replaced
| -1:000000000000 | 0:191a9b40b08d |
|---|---|
| 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 'c' over the sorted index range | |
| 18 * [begin, end) for an index 'i' where 'c[i] == target'. If such an index 'i' is | |
| 19 * found, BinarySearch returns 'true' and the index is returned via the outparam | |
| 20 * 'matchOrInsertionPoint'. If no index is found, BinarySearch returns 'false' | |
| 21 * and the outparam returns the first index in [begin, end] where 'target' can | |
| 22 * 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 template <typename Container, typename T> | |
| 34 bool | |
| 35 BinarySearch(const Container &c, size_t begin, size_t end, T target, size_t *matchOrInsertionPoint) | |
| 36 { | |
| 37 MOZ_ASSERT(begin <= end); | |
| 38 | |
| 39 size_t low = begin; | |
| 40 size_t high = end; | |
| 41 while (low != high) { | |
| 42 size_t middle = low + (high - low) / 2; | |
| 43 const T &middleValue = c[middle]; | |
| 44 | |
| 45 MOZ_ASSERT(c[low] <= c[middle]); | |
| 46 MOZ_ASSERT(c[middle] <= c[high - 1]); | |
| 47 MOZ_ASSERT(c[low] <= c[high - 1]); | |
| 48 | |
| 49 if (target == middleValue) { | |
| 50 *matchOrInsertionPoint = middle; | |
| 51 return true; | |
| 52 } | |
| 53 | |
| 54 if (target < middleValue) | |
| 55 high = middle; | |
| 56 else | |
| 57 low = middle + 1; | |
| 58 } | |
| 59 | |
| 60 *matchOrInsertionPoint = low; | |
| 61 return false; | |
| 62 } | |
| 63 | |
| 64 } // namespace mozilla | |
| 65 | |
| 66 #endif // mozilla_BinarySearch_h |
