Navigation
Understanding the simplest way to find an item in a list by checking every single one.
Imagine you are looking for your favorite blue socks in a messy drawer. You don't know where they are, so you pick up every single sock one by one until you find the blue pair. Did you know you were actually acting like a computer algorithm?
In computer science, a Linear Search (also called a sequential search) is the simplest way to find a specific value in a list. Imagine you have a row of lockers and you are looking for the one containing a golden trophy. Since you don't have a map, you start at the very first locker, open it, and check inside. If the trophy isn't there, you move to the second locker, then the third, and so on. You keep going in a straight line until you either find the trophy or reach the very last locker. This algorithm is robust, meaning it works even if the items are completely jumbled up and not in any specific order.
Let's find the number in this list:
1. Step 1: Look at the first item (). Is ? No. Move to the next. 2. Step 2: Look at the second item (). Is ? No. Move to the next. 3. Step 3: Look at the third item (). Is ? No. Move to the next. 4. Step 4: Look at the fourth item (). Is ? Yes! Stop the search.
Quick Check
Where does a linear search always begin its search?
Answer
It always starts at the very first item (the beginning) of the list.
Computers use a loop to perform a linear search. A loop tells the computer to repeat an action over and over. Inside the loop, the computer asks a simple question: 'Is the current item equal to the target item?' This is a Boolean question because the answer is either True or False. If the answer is True, the computer returns the position of the item and stops. If the computer reaches the end of the list without finding a match, it usually returns a message like 'Not Found' or a special value like .
Search for 'Grapes' in this grocery list: ['Apple', 'Banana', 'Pear']
1. Check Index 0: Is 'Apple' == 'Grapes'? False. 2. Check Index 1: Is 'Banana' == 'Grapes'? False. 3. Check Index 2: Is 'Pear' == 'Grapes'? False. 4. End of List: There are no more items. The computer reports 'Not Found'.
Quick Check
If a list has items, what is the maximum number of checks a linear search might have to do?
Answer
The maximum number of checks is .
We measure the efficiency of algorithms by looking at the worst-case scenario. In a linear search, the worst case happens if the item you want is at the very end of the list or not there at all. If your list has items, you do checks. If it has items, you might have to do checks! This relationship is called linear time complexity. Because the time it takes grows at the same rate as the list size, we say it has a 'Big O' notation of . While it is easy to program, it can be very slow for massive databases like Google Search or YouTube's video library.
Imagine a computer can check item every millisecond ().
1. For a list of items, the longest search takes . 2. For a list of items, the longest search takes (which is seconds). 3. If the list grows to items, the search could take seconds (nearly minutes!).
This shows why linear search is best for small or unsorted lists.
In the 'Best Case' scenario, how many items does a linear search check?
Which of these is a requirement for performing a linear search?
As a list gets 10 times larger, a linear search could take up to 10 times longer to find an item.
Review Tomorrow
Tomorrow, try to explain the 'locker analogy' to a friend or family member without looking at this guide.
Practice Activity
Take a shuffled deck of cards and try to find the Ace of Spades by flipping them one by one. Count how many cards you had to flip—that's a manual linear search!