Search algorithms

Linear Search

In an non-ordered array, we go from start to finish and ask at each index position if the value we want is present.

export default function linear_search(haystack: number[], needle: number): boolean {
    for (let i = 0; i < haystack.length; i++) {
        if(haystack[i] === needle) {
            return true
        }
    }
    return false
}

The Big O of linear search is O(N).

Binary Search

The binary in binary search refers to the 0 or 1 aspect of binary, and does not mean working with actual binary values.

In an ordered array, we go to its middle, check if the value is equal to the one we are looking for. If it's not, we check if it's greater/smaller than the value we are looking for, exclude the half part that does not contain it, and repeat this process on the half we kept, until there is only one value left: either the one we are looking for, or another one, which means our value is not inside the array.

export default function bs_list(haystack: number[], needle: number): boolean {
    let lo = 0
    let hi = haystack.length
 
    do {
        let m = Math.floor(lo - (hi - lo) / 2)
        let v = haystack[m]
 
        if(v === needle) {
            return true
        } else if (v > needle) {
            hi = m // Exclude the right part of the array
        } else {
            lo = m + 1 // Exclude the left side of the array + the m value
        }
    } while (lo < hi)
 
    return false
}

The Big O of Binary Search is O(log n).

Exercise: The two crystal balls

In this exercise, the building is an array, and the value of breaks is either false (did not break) or true (did break).

In this case, both the Linear Search and the Binary Search can work but won't be optimal:

1. The Linear Search will only use one crystal ball and will be very slow, testing every floor one after the other.
2. The Binary Search, with its base number of 2, would only be able to approximate the height, as it only get two tries.

A better solution would be:

1. Jump every x in the array and check if the first ball breaks
2. When the ball breaks, walk backwards to the amount of x
3. Walk forward linearly until the second ball breaks

Since we don't want to use a constant to determine x as it would not be proportional to the array size, we change its unit type, and use the square root of the array.

export default function two_crystal_balls(breaks: boolean[]): number {
 
    const jmpAmount = Math.floor(Math.sqrt(breaks.length))
    let i = jmpAmount
 
    for (; i < breaks.length; i += jmpAmount) {
        if(breaks[i]) {
            break // Stop jumping if first ball breaks
        }
    }
 
    i -= jmpAmount // Walk back the distance of the jump
 
    for (let j = 0; j < jmpAmount && i < breaks.length; ++j, ++i) {
    if(breaks[i]) {
            return i // Return when second ball breaks
        }
    }
 
    return -1
}

The Big O for this algorithm is O(√n).