Exercises from the "Grokking Algorithms" book

ch1-binarySearch.ts

function binarySearch(list: number[], item: number) {
    let low = 0
    let high = list.length - 1

    while (low <= high) {
        let mid = Math.floor((low + high) / 2)
        let guess = list[mid]

        if (guess === item) {
            return mid
        }
        if (guess > item) {
            high = mid - 1
        } else {
            low = mid + 1
        }
    }

    return null
}

const myList = [1, 3, 5, 7, 9]

console.log(binarySearch(myList, 3))
console.log(binarySearch(myList, -1))

ch2-selectionSort.ts

function findSmallest(arr: number[]): number {
    let smallest = arr[0]
    let smallestIndex = 0

    for (let i = 1; i < arr.length; i++) {
        if (arr[i] < smallest) {
            smallest = arr[i]
            smallestIndex = i
        }
    }

    return smallestIndex
}

function selectionSort(arr: number[]): number[] {
    let newArr: number[] = []
    const elementCount = arr.length

    for (let i = 0; i < elementCount; i++) {
        let smallest = findSmallest(arr)
        newArr.push(arr[smallest])
        arr.splice(smallest, 1)
    }

    return newArr
}

console.log(selectionSort([5, 3, 6, 2, 10]))

ch4-binarySearch.ts

function binarySearch(list: number[], item: number): number|null {
    if (list.length === 0) {
        return null
    }

    let low = 0
    let high = list.length - 1

    let mid = Math.floor((low + high) / 2)

    let guess = list[mid]

    if (guess === item) {
        return mid
    }

    if (guess > item) {
        return binarySearch(list.slice(0, mid), item)
    } else {
        const result = binarySearch(list.slice(mid + 1), item)

        return result !== null ? (mid + 1) + result : null
    }
}

const myList = [1, 3, 5, 7, 9]

console.log(binarySearch(myList, 3))
// console.log(binarySearch(myList, -1))

ch4-listCount.ts

function listCount(arr: any[]):number {
    if (arr.length === 0) {
        return 0
    }

    return 1 + listCount(arr.slice(1))
}

console.log(listCount([1, 2, 3, 4]))
console.log(listCount([2, 4, 6]))

ch4-maxNumber.ts

function findMax(arr: number[]):number {
    if (arr.length === 0) {
        return 0
    }

    const leftItem = arr[0]
    const rightItem = findMax(arr.slice(1))

    return leftItem > rightItem ? leftItem : rightItem
}

console.log(findMax([1, 2, 3, 4]))
console.log(findMax([2, 4, 6]))

ch4-quicksort.ts

function quicksort(arr: number[]): number[] {
    if (arr.length < 2) {
        return arr
    } else {
        const pivot = arr[0]

        const less = arr.slice(1).filter(item => item <= pivot)
        const greater = arr.slice(1).filter(item => item > pivot)

        return [...quicksort(less), pivot, ...quicksort(greater)]
    }
}

console.log(quicksort([10, 5, 2, 3]))

ch4-sum.ts

function sum(arr: number[]):number {
    if (arr.length === 0) {
        return 0
    }

    return arr[0] + sum(arr.slice(1))
}

console.log(sum([1, 2, 3, 4]))
console.log(sum([2, 4, 6]))