Comp 110 Searching with Arrays

Searching with Arrays

To search through arrays, we can use either linear or binary search.

Linear Search

With linear search, we start with the array we want to search through and the item we are looking for. With linear search, we start at one end of the array and check each element until we find what we want. This takes on average N / 2 to complete.

An example of linear search:

let findTheNum = (numbers: number[], item: number): boolean => {
    let i: number = 0;
    while (i < numbers.length) {
        if (numbers[i] === item) {
            return true;
        }
        i++;
    }
    return false;
};
print(findTheNum([0, 1, 2, 3], 2)); // prints true

The function in the above example will take in an array of numbers. It also takes in a number, which is the number we're searching for in our array. It looks through each element in the array until it finds that number, at which point it returns true. If it makes it all the way through the array without finding the number, it returns false.

Binary Search

For binary search, an important requirement is that we need the elements in our array to be sorted before we search through the array. We start our search in the middle of the array, and if the element we're at is too big we go on to check the lower half of the array. If it's too small, we check next in the larger half. Once we decide which half to move to next, we start in the middle of this half. Each additional step of our search cuts the search space in half. To find the next index we want to check, we use this general formula:

middle = Math.floor((low + high) / 2)

For an example of binary search, we'll use the ascending function as our comparator function:

export interface Comparator<t> {
    (a: T, b: T): number;
}
 
export const A_BEFORE_B: number = -1;
export const A_SAME_AS_B: number = 0;
export const A_AFTER_B: number = 1;</t>
 
let ascending = (a: string, b: string): number => {
    if (a < b) {
        return A_BEFORE_B;
    } else if (a === b) {
        return A_SAME_AS_B;
    } else {
        return A_AFTER_B;
    }
};

Now for our example:

let binS = (ar: string[], val: string, compare): boolean => {
    let low = 0; // starting low value
    let high = ar.length - 1; // biggest index--high value
    while (low <= high) {
        let middle = Math.floor((low + high) / 2);
        let comparison = compare(val, ar[middle]);
        if (comparison === A_BEFORE_B) {
            high = middle - 1;
        } else if (comparison === A_AFTER_B) {
            low = middle + 1;
        } else {
            return true;
        }
    }
    return false;
};
print(binS(["another", "array", "of", "some", "words"], "some", ascending));
// prints true

Binary search takes about log(N) steps to complete.