1 | /**
|
---|
2 | * Copyright 2019 The AMP HTML Authors. All Rights Reserved.
|
---|
3 | *
|
---|
4 | * Licensed under the Apache License, Version 2.0 (the "License");
|
---|
5 | * you may not use this file except in compliance with the License.
|
---|
6 | * You may obtain a copy of the License at
|
---|
7 | *
|
---|
8 | * http://www.apache.org/licenses/LICENSE-2.0
|
---|
9 | *
|
---|
10 | * Unless required by applicable law or agreed to in writing, software
|
---|
11 | * distributed under the License is distributed on an "AS IS" BASIS,
|
---|
12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
|
---|
13 | * See the License for the specific language governing permissions and
|
---|
14 | * limitations under the License.
|
---|
15 | */
|
---|
16 | /**
|
---|
17 | * A binary search implementation that returns the index if a match is found,
|
---|
18 | * or the negated index of where the `needle` should be inserted.
|
---|
19 | *
|
---|
20 | * The `comparator` callback receives both the `item` under comparison and the
|
---|
21 | * needle we are searching for. It must return `0` if the `item` is a match,
|
---|
22 | * any negative number if `item` is too small (and we must search after it), or
|
---|
23 | * any positive number if the `item` is too large (and we must search before
|
---|
24 | * it).
|
---|
25 | *
|
---|
26 | * If no match is found, a negated index of where to insert the `needle` is
|
---|
27 | * returned. This negated index is guaranteed to be less than 0. To insert an
|
---|
28 | * item, negate it (again) and splice:
|
---|
29 | *
|
---|
30 | * ```js
|
---|
31 | * const array = [1, 3];
|
---|
32 | * const needle = 2;
|
---|
33 | * const index = binarySearch(array, needle, (item, needle) => item - needle);
|
---|
34 | *
|
---|
35 | * assert.equal(index, -2);
|
---|
36 | * assert.equal(~index, 1);
|
---|
37 | * array.splice(~index, 0, needle);
|
---|
38 | * assert.deepEqual(array, [1, 2, 3]);
|
---|
39 | * ```
|
---|
40 | */
|
---|
41 | export default function binarySearch<T, S>(haystack: ArrayLike<T>, needle: S, comparator: (item: T, needle: S) => number, low: number, high: number): number;
|
---|