<

Go Premium for a chance to win a PS4. Enter to Win

x

Linear Search

Published on
3,778 Points
678 Views
1 Endorsement
Last Modified:
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.
 
In best case, it will be the first car
In worst case, is will be the 100th car
In average case, it will be (1 + 100) / 2 = 50.5 or 50th car

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;
}

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.
1
Comment
0 Comments

Featured Post

How to Use the Help Bell

Need to boost the visibility of your question for solutions? Use the Experts Exchange Help Bell to confirm priority levels and contact subject-matter experts for question attention.  Check out this how-to article for more information.

Join & Write a Comment

Suggested Articles

I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…
Exchange organizations may use the Journaling Agent of the Transport Service to archive messages going through Exchange. However, if the Transport Service is integrated with some email content management application (such as an anti-spam), the admin…
Suggested Courses

Keep in touch with Experts Exchange

Tech news and trends delivered to your inbox every month