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.
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.
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:
That pseudocode can be used to implement a working linear search:
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:
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.
-
Incorrect
Correct
No Answer was selected
Invalid Answer
How does Linear Search work?
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.