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 47 48 49 50 51 52 | 1x 1x 1x 1x 1x 1x 1x 1x 32x 32x 32x 32x 61x 61x 61x 61x 26x 26x 26x 61x 28x 28x 28x 61x 25x 25x 32x 1x 1x 1x 6x 6x 6x 6x 6x 6x 6x 6x 3x 3x 3x 6x 3x 3x 3x 3x 3x 3x 3x | /**
* binary search a sorted array
* return the index of the number if found or -1 if not found
*/
export const binarySearch = (
arr: number[] | string[],
search: number | string
) => {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
const middle = Math.round((right + left) / 2);
if (arr[middle] === search) return middle;
if (arr[middle] > search) {
// move right
right = middle - 1;
}
if (arr[middle] < search) {
// move left
left = middle + 1;
}
}
return -1;
};
// binary search with recursion
export const binarySearchRecursion = (
arr: number[] | string[],
search: number | string,
offset: number = 0
): number => {
const middle = Math.floor(arr.length / 2);
// base case
if (arr[middle] === search) return offset + middle;
if (arr.length === 0) return -1;
// recursion case
if (arr[middle] > search)
return binarySearchRecursion(arr.slice(0, middle), search, offset);
if (arr[middle] < search)
return binarySearchRecursion(
arr.slice(middle + 1),
search,
offset + middle + 1
);
return -1;
};
|