Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 | 13x 8x 5x 2x 3x 11x 11x 3x 8x 3x 5x 1x 4x 6x | /*!
* Copyright (c) Microsoft. All rights reserved.
* Licensed under the MIT license. See LICENSE file in the project.
*/
// Hackerrank.com? shows up on bing if I search for binary search
/**
* Performs numerical comparison
*/
export function DEFAULT_COMPARE<T>(item1: T, item2: T): number {
if (item1 < item2) {
return -1
} else if (item1 > item2) {
return 1
}
return 0
}
/**
* Performs a binary search on the given array
* @param array - The array of numbers to search
* @param item - The item to look for
* @returns index of found item
*/
export function binarySearch<T = number>(
array: T[],
item: T,
compare = DEFAULT_COMPARE,
): number {
function binarySearchRec(left: number, right: number): number {
const mid = Math.floor((left + right) / 2)
if (left > right) {
return -1
}
if (compare(array[mid], item) === 0) {
return mid
}
if (compare(array[mid], item) > 0) {
return binarySearchRec(left, mid - 1)
}
return binarySearchRec(mid + 1, right)
}
return binarySearchRec(0, array.length - 1)
}
|