Linear Search – [OLD – FALL 2016] 15-104 • COMPUTING for CREATIVE PRACTICE

“Linear Search” is a basic algorithm: How do I find something in an array of things?

Template for Linear Search

for each element of the array:
    Is this the element I’m looking for?
        If yes, return the location
    Otherwise, continue with the next element

function searchArrayForSomething(anArray, something) {
    for (var i = 0; i < anArray.length; i++) {
        if (anArray[i] == something) {
            return i; // the location of something
        }
    }
    return -1; // something was not found
}

// here's how it might be used:
    var locationOfSomething = searchArrayForSomething(myArray, x);
    if (locationOfSomething > -1) {
        println("I found " + something + " at index " + locationOfSomething);
    }

function searchArrayForSomething(anArray, something) {

for (var i = 0; i < anArray.length; i++) {

if (anArray[i] == something) {

return i; // the location of something

}

return -1; // something was not found

}

// here's how it might be used:

var locationOfSomething = searchArrayForSomething(myArray, x);

if (locationOfSomething > -1) {

println("I found " + something + " at index " + locationOfSomething);

}

Finding the Largest Element

Linear search can also be used to find items with some property or to find the largest or smallest thing.

Here’s a template for finding the smallest thing:

function smallest(anArray) {
    // start with a candidate smallest item
    var smallestVal = anArray[0];
    // and it's location
    var indexOfSmallest = 0;
    // then search to see if anything is smaller
    for (var i = 0; i < anArray.length; i++) {
        if (anArray[i] < smallest) {
            // found something smaller, remember the smallest so far:
            smallestVal = anArray[i];
            indexOfSmallest = i;
        }
    }
    return indexOfSmallest;
}

    // here's how to use the function
    var loc = smallest(myArray);
    println("The smallest value, " + myArray[loc] + " is at location " + loc);

function smallest(anArray) {

// start with a candidate smallest item

var smallestVal = anArray[0];

// and it's location

var indexOfSmallest = 0;

// then search to see if anything is smaller

for (var i = 0; i < anArray.length; i++) {

if (anArray[i] < smallest) {

// found something smaller, remember the smallest so far:

smallestVal = anArray[i];

indexOfSmallest = i;

}

return indexOfSmallest;

}

// here's how to use the function

var loc = smallest(myArray);

println("The smallest value, " + myArray[loc] + " is at location " + loc);

Analysis

How many steps does it take to find something with linear search?

In general, we have to step through each element of the array. Even if we’re searching for things at arbitrary locations, we can expect to search half the array.

If we search the whole array, we loop array.length times. The cost of each iteration depends on many factors, but at least we can say the cost is proportional to the length of the array. Sometimes we write this O(array.length). Often, we use the variable N to mean “the size of the problem”, in this case, the size of the array, so the cost of the search is O(N). (Pronounced either “Order N” or “Big-Oh of N”).

If we search half the array, we loop array.length/2 times. The cost of each iteration depends on many factors, and we have a factor of 1/2 as well, but at least we can say the cost is (again) proportional to the length of the array. Thus, this also costs O(array.length) or O(N).

Bottom line: Linear Search is an O(N) algorithm.

Are there faster ways to search? How does Google work?