Please enable JavaScript to use CodeHS

Chapter 7

ArrayLists

7.5 Searching

As the amount of data stored in an array or ArrayList begins to grow, a common necessity is knowing where and if certain data can be found within a dataset. For example, a user is interested in buying a new car. They want to find a used car that is within their price range and a certain color. Given a database of cars, this user should be able to find the exact car that they are looking for, provided that the car exists in the database! This process of finding data, or pieces of data, that fit a specific criteria is called searching.

Linear Search

A common way to search through a list of items is to start at the beginning of the list and continue through the list until the desired item is found. If the desired item is not found, then that means it is not in the list.

Suppose that you are given a set of raffle tickets at a school raffle. Each ticket has its own number on it:

Ticket 0 1 2 3 4 5
Number 44 53 12 51 64 15

The 0th ticket has number 44, and the ticket at index 4 has raffle number 64. The school will randomly select a number between 1 and 100. If you have the ticket with that number, you win!
What if the school picks 51 as the winning number? As a human, it’s easy to look over the whole list and see that you have the ticket with 51 on it, but computers need a more programmatic approach to looking through the list.

The process of searching each item in a list until the desired item is found is called linear, or sequential search.

Implementing Linear Search

Linear search is fairly easy to implement. To programmatically search the list of raffle ticket numbers, you just need to iterate through the list one number at a time. At each new number, if the number matches the desired number, then the desired number is in the list, and the program can stop searching and return the index position of the number. If the program makes it all the way to the end of the list and hasn’t spotted the desired number, then that means it’s not in the list.

Here’s what it looks like in pseudocode:

for every index in the list:
get the current number at that index position
if the current number matches our target number:
return the index
return not found
Plain text

That pseudocode can be used to implement a working linear search:

public int linearSearch(int[] array, int key)
{
    for(int i = 0; i < array.length; i++)
    {
        int element = array[i];
        if(element == key)
        {
            return i;
        }
    }
    return -1;
}
Plain text

In the example above, key represents the value that is being searched for in the given list. If the key is an element in the list, then the index where that value can be found is returned to the program, otherwise, the value -1 will be returned.

This method can also be implemented using ArrayList:

public int linearSearch(ArrayList<Integer> arrayL, int key)
{
    for(int i = 0; i < arrayL.size(); i++)
    {
        int element = arrayL.get(i);
        if(element == key)
        {
            return i;
        }
    }
    return -1;
}
Plain text

While linear search is a fairly easy algorithm to implement and understand, linear search is limited by the number of elements that are being searched. The longer the data set is, the longer linear search takes, as it must iterate through all values in order to find the correct one.

Suppose the 1 millionth item in a data set were the element that you were looking for- linear search would have to iterate through the data set 1 million times in order to find it! When deciding how to search for values in a data set, it’s important to consider the pros and cons of using the search mechanism.

Linear Search

Check Your Understanding

  1. Incorrect Correct No Answer was selected Invalid Answer

    How does Linear Search work?

Exercise: Linear Search on ArrayList with While Loop

In this exercise, you should implement a method to do linear search on an ArrayList of Doubles and return the index of the search Double, or -1 if it isn’t found using a while loop.