1// Copyright (C) 2018 The Android Open Source Project 2// 3// Licensed under the Apache License, Version 2.0 (the "License"); 4// you may not use this file except in compliance with the License. 5// You may obtain a copy of the License at 6// 7// http://www.apache.org/licenses/LICENSE-2.0 8// 9// Unless required by applicable law or agreed to in writing, software 10// distributed under the License is distributed on an "AS IS" BASIS, 11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12// See the License for the specific language governing permissions and 13// limitations under the License. 14 15type Numeric = number | bigint; 16type Range = [number, number]; 17 18function searchImpl<T extends Numeric>( 19 haystack: ArrayLike<T>, 20 needle: T, 21 i: number, 22 j: number, 23): number { 24 if (i === j) return -1; 25 if (i + 1 === j) { 26 return needle >= haystack[i] ? i : -1; 27 } 28 29 const mid = Math.floor((j - i) / 2) + i; 30 const midValue = haystack[mid]; 31 if (needle < midValue) { 32 return searchImpl(haystack, needle, i, mid); 33 } else { 34 return searchImpl(haystack, needle, mid, j); 35 } 36} 37 38function searchRangeImpl<T extends Numeric>( 39 haystack: ArrayLike<T>, 40 needle: T, 41 i: number, 42 j: number, 43): Range { 44 if (i === j) return [i, j]; 45 if (i + 1 === j) { 46 if (haystack[i] <= needle) { 47 return [i, j]; 48 } else { 49 return [i, i]; 50 } 51 } 52 53 const mid = Math.floor((j - i) / 2) + i; 54 const midValue = haystack[mid]; 55 56 if (needle < midValue) { 57 return searchRangeImpl(haystack, needle, i, mid); 58 } else if (needle > midValue) { 59 return searchRangeImpl(haystack, needle, mid, j); 60 } else { 61 while (haystack[i] !== needle) i++; 62 while (haystack[j - 1] !== needle) j--; 63 return [i, j]; 64 } 65} 66 67// Given a sorted array of numeric values |haystack| and a |needle|, return the 68// index of the last element of |haystack| which is less than or equal to 69// |needle|, or -1 if all elements of |haystack| are greater than |needle|. 70export function search<T extends Numeric>( 71 haystack: ArrayLike<T>, 72 needle: T, 73): number { 74 return searchImpl(haystack, needle, 0, haystack.length); 75} 76 77// Given a sorted array of numeric values (|haystack|) return the half open 78// range [i, j) of indices where |haystack| is equal to needle. 79export function searchEq<T extends Numeric>( 80 haystack: ArrayLike<T>, 81 needle: T, 82 optRange?: Range, 83): Range { 84 const range = searchRange(haystack, needle, optRange); 85 const [i, j] = range; 86 if (haystack[i] === needle) return range; 87 return [j, j]; 88} 89 90// Given a sorted array of numeric values (|haystack|) and a |needle| return the 91// smallest half open range [i, j) of indexes which contains |needle|. 92export function searchRange<T extends Numeric>( 93 haystack: ArrayLike<T>, 94 needle: T, 95 optRange?: Range, 96): Range { 97 const [left, right] = optRange ? optRange : [0, haystack.length]; 98 return searchRangeImpl(haystack, needle, left, right); 99} 100 101// Given a sorted array of numeric values (|haystack|) and a |needle| return a 102// pair of indexes [i, j] such that: 103// If there is at least one element in |haystack| smaller than |needle| 104// i is the index of the largest such number otherwise -1; 105// If there is at least one element in |haystack| larger than |needle| 106// j is the index of the smallest such element otherwise -1. 107// 108// So we try to get the indexes of the two data points around needle 109// or -1 if there is no such datapoint. 110export function searchSegment<T extends Numeric>( 111 haystack: ArrayLike<T>, 112 needle: T, 113): Range { 114 if (!haystack.length) return [-1, -1]; 115 116 const left = search(haystack, needle); 117 if (left === -1) { 118 return [left, 0]; 119 } else if (left + 1 === haystack.length) { 120 return [left, -1]; 121 } else { 122 return [left, left + 1]; 123 } 124} 125