Binary search in JS

binary_search_js_iterative.md

Features:

• Returns the index of the search value if found, otherwise, undefined
• No array copy
• Iterative

function binarySearch(arr, number) {
    let start = 0
    let end = arr.length - 1

    while (start <= end) {
        let midIndex = Math.floor((start + end) / 2)
        let midpoint = arr[midIndex]

        if (midpoint == number) {
            return midIndex
        }
        else if (number < midpoint) {
            end = midIndex - 1
        }
        else {
            start = midIndex + 1
        }   
    }
}

With debugging:

function binarySearch(arr, number) {
    let start = 0
    let end = arr.length - 1

    while (start <= end) {
        console.log('arr slice', arr.slice(start, end + 1))
        console.log('start', start)
        console.log('end', end)

        let midIndex = Math.floor((start + end) / 2)
        let midpoint = arr[midIndex]

        console.log('midIndex', midIndex)
        console.log('midpoint', midpoint)

        if (midpoint == number) {
            return midIndex
        }
        else if (number < midpoint) {
            end = midIndex - 1
        }
        else {
            start = midIndex + 1
        }     
    }
}

Output is the same as the recursive version.

binary_search_js_recursive.md

Features:

• Returns the index of the search value if found, otherwise, undefined
• No array copy
• Recursive

function binarySearch(arr, number, start = 0, end = arr.length - 1) {
    if (start >= end) return

    let midIndex = Math.floor((start + end) / 2)
    let midpoint = arr[midIndex]
    
    if (midpoint == number) return midIndex

    if (number < midpoint) return binarySearch(arr, number, start, midIndex - 1)

    return binarySearch(arr, number, midIndex + 1, end)
}

With debugging:

function binarySearch(arr, number, start = 0, end = arr.length - 1) {
    if (start >= end) return

    console.log('arr slice', arr.slice(start, end + 1))
    console.log('start', start)
    console.log('end', end)
    let midIndex = Math.floor((start + end) / 2)
    let midpoint = arr[midIndex]

    console.log('midIndex', midIndex)
    console.log('midpoint', midpoint)
    
    if (midpoint == number) return midIndex

    if (number < midpoint) return binarySearch(arr, number, start, midIndex - 1)

    return binarySearch(arr, number, midIndex + 1, end)
}

Output when the search value is near the start of the list:

binarySearch([1, 2, 3, 4, 5, 7, 10, 20, 21, 56], 4)
> arr slice (10) [1, 2, 3, 4, 5, 7, 10, 20, 21, 56]
> start 0
> end 9
> midIndex 4
> midpoint 5
> arr slice (4) [1, 2, 3, 4]
> start 0
> end 3
> midIndex 1
> midpoint 2
> arr slice (2) [3, 4]
> start 2
> end 3
> midIndex 2
> midpoint 3
> arr slice [4]
> start 3
> end 3
> midIndex 3
> midpoint 4
> 3

Output when the search value is near the end of the list:

binarySearch([1, 2, 3, 4, 5, 7, 10, 20, 21, 56], 21)
> arr slice (10) [1, 2, 3, 4, 5, 7, 10, 20, 21, 56]
> start 0
> end 9
> midIndex 4
> midpoint 5
> arr slice (5) [7, 10, 20, 21, 56]
> start 5
> end 9
> midIndex 7
> midpoint 20
> arr slice (2) [21, 56]
> start 8
> end 9
> midIndex 8
> midpoint 21
> 8

Output when the search value is not in the list:

binarySearch([1, 2, 3, 4, 5, 7, 10, 20, 21, 56], 15)
> arr slice (10) [1, 2, 3, 4, 5, 7, 10, 20, 21, 56]
> start 0
> end 9
> midIndex 4
> midpoint 5
> arr slice (5) [7, 10, 20, 21, 56]
> start 5
> end 9
> midIndex 7
> midpoint 20
> arr slice (2) [7, 10]
> start 5
> end 6
> midIndex 5
> midpoint 7
> arr slice [10]
> start 6
> end 6
> midIndex 6
> midpoint 10
> undefined