Linear Search

Suppose you use Uber application as a rider and you request a ride to go from one place to another. Your driver just arrived at the parking lot of your place. The only thing you know about the ride is the license plate number. How do you find your Uber ride?

The obvious thing is to go to the parking lot and search all the cars one by one. This method of searching is called linear search, where we search for all possible options (brute force search) until we get our desired result. We follow linear search in our daily life such as while finding a specific book, medicine or movie in stores.

Going back to Uber example, let’s consider parking lot as an array of cars (an array is a series of objects or elements of the same type). If there are 100 cars then the car you are looking for can be any car in the range of first to 100th.
 

Here is a coding example for a linear search in Java. For simplicity we can assume that license plate number is represented as integer numbers. The algorithm below describes how to perform a linear search operation to find license number. There is an array that contains all the cars.

First, we find length of the array (total number of cars). For each index (low to high) we'll check if an item in that index is equal to our required number. If it is, then we stop and return that index number. If not, we keep checking. If all numbers have been checked and we haven't found our result then we assume that number is not present in the array. The array has 100 cars where 0th index represents 001th car, 1th index represents 002th car, .........99th index represents 100th car. If there arises a situation where current index is 99 but a match has not been found we can conclude that there is no such car in our array. As the search failed to return result, the algorithm returns -1 indicating our search result is negative.
 

//searchMyRide() takes two parameters
                      //1. cars: list of all the license plate number in the parking lot
                      //2. required_license_number: license plate number we are looking for
                      //This returns an integer indicating the position of the in the 0 based array.
                      //If the car is not found we can return a negative integer.
                      public int searchMyRide(int[] cars, int required_license_number) 
                      {
                         int total_cars = cars.length;
                         for(int index = 0; index < total_cars; ++index) 
                         {
                           if(cars[index].getLiceseNumber().equals(required_license_number)) 
                           {
                                // We found our car, return the position of the car in the array.
                                return index;
                            }
                         }
                         // Car not found, let’s return -1 to indicate that car not found.
                         return -1;
                      }
                      

Select all Open in new window

Complexity
All possible values are visited in linear search algorithm. If there are N items in an array, it takes O(N) comparisons to search an item.