Skip to main content

Linear Search


Linear search is a method for finding a specific value in a list or array by iterating through each element in the list or array until the desired value is found. This method is also known as a sequential search. It is a simple search algorithm that is easy to understand and implement.

The basic idea behind linear search is to start at the first element in the list or array and compare it to the desired value. If the element is not the desired value, the algorithm moves on to the next element and continues this process until the desired value is found or the end of the list or array is reached.

One advantage of linear search is that it is easy to implement and understand, making it a good choice for small lists or arrays. Additionally, linear search does not require any pre-processing of the data and can be applied to any data type.

However, the main disadvantage of linear search is its time complexity. The time it takes to find a specific value in a list or array using linear search is directly proportional to the size of the list or array. For large lists or arrays, the search can take a significant amount of time.

One way to improve the time complexity of linear search is to implement a more efficient search algorithm, such as binary search. Binary search works by repeatedly dividing the list or array in half and eliminating half of the remaining possibilities with each iteration. This results in a time complexity of O(log n) which is much faster than linear search.

In practice, linear search is used in simple cases where the number of elements is small and or the data is not sorted, and the data is not large.

Another variation of linear search is known as a sentinel linear search, in which the last element of the array is replaced with the value being searched for. This eliminates the need to check if the end of the array has been reached and can improve the performance of the search.

Linear search is a basic search algorithm that is easy to understand and implement, but it can be slow for large lists or arrays. More efficient search algorithms, such as binary search, should be used when the number of elements is large and the data is sorted.


PSEUDO CODE:




This is a basic implementation of the linear search algorithm. It takes a list and an item to search for as its inputs. The function iterates through each element in the list using a for loop, starting at the first element and ending at the last element. If the current element is equal to the item being searched for, the function returns the index of that element. If the end of the loop is reached and the item has not been found, the function returns None.

Linear search is a simple algorithm to find an item in a list by checking every element in the list one by one. It's time complexity is O(n).


PYTHON CODE:

Here is an example of linear search implemented in Python:



The function takes in two arguments, the list arr and the value x to search for. Inside the for loop, the function checks if each element of the list is equal to x. If a match is found, the function returns the index of that element. If the end of the loop is reached without finding a match, the function returns -1.

In the example above, the function is called with an example list arr and the value x to search for. The result of the function call is then checked and the appropriate message is printed to the console.


JAVA CODE:


Here is an example of linear search implemented in Java:



In this example, the search() method takes in two arguments, an array arr and an integer x to search for. Inside the for loop, the method checks if each element of the array is equal to x. If a match is found, the method returns the index of that element. If the end of the loop is reached without finding a match, the method returns -1.

In the main() method, the example array arr and the value x to search for are defined. The search() method is called with these arguments and the result is stored in the variable result. The result of the function call is then checked and the appropriate message is printed to the console.


C CODE:


Here is an example of linear search implemented in C:



In this example, the search() function takes in three arguments, an array arr, an integer n representing the size of the array and an integer x to search for. Inside the for loop, the function checks if each element of the array is equal to x. If a match is found, the function returns the index of that element. If the end of the loop is reached without finding a match, the function returns -1.

In the main() function, the example array arr and the value x to search for are defined. The size of the array is calculated and passed as an argument to the search() function. The function is called with these arguments and the result is stored in the variable result. The result of the function call is then checked and the appropriate message is printed to the console.

C++ CODE:


Here is an example of linear search implemented in C++:



In this example, the search() function takes in three arguments, an array arr, an integer n representing the size of the array and an integer x to search for. Inside the for loop, the function checks if each element of the array is equal to x. If a match is found, the function returns the index of that element. If the end of the loop is reached without finding a match, the function returns -1.

In the main() function, the example array arr and the value x to search for are defined. The size of the array is calculated and passed as an argument to the search() function. The function is called with these arguments and the result is stored in the variable result. The result of the function call is then checked and the appropriate message is printed to the console.

JAVASCRIPT CODE:


Here is an example of linear search implemented in JavaScript:




In this example, the linearSearch() function takes in two arguments, an array arr and an element x to search for. Inside the for loop, the function checks if each element of the array is equal to x. If a match is found, the function returns the index of that element. If the end of the loop is reached without finding a match, the function returns -1.

In the example above, the function is called with an example array arr and the value x to search for. The result of the function call is then checked and the appropriate message is printed to the console.

Comments

Post a Comment

Popular posts from this blog

Bubble Sort

   Bubble sort is a simple sorting algorithm that works by repeatedly swapping adjacent elements if they are in the wrong order. It is named after the way bubbles rise to the top of a liquid, as it sorts the array by repeatedly moving the largest or smallest elements to the top of the array. The algorithm works by iterating through the array, comparing each adjacent pair of elements and swapping them if they are in the wrong order. This process is repeated until the array is fully sorted. Let's say we have an array of integers [5, 3, 8, 4, 2]. The first pass of the algorithm would compare 5 and 3, swap them to get [3, 5, 8, 4, 2]. It would then compare 5 and 8 and not swap them, as they are in the correct order. It would then compare 8 and 4, swap them to get [3, 5, 4, 8, 2]. It would then compare 8 and 2, swap them to get [3, 5, 4, 2, 8]. The first pass is now complete, and the largest element, 8, is at the end of the array. The second pass would start with comparing 3 and 5,...

Pigeonhole Sort

Pigeonhole sort is a sorting algorithm that works by distributing elements of an input sequence into a set of pigeonholes or buckets. It is an efficient sorting algorithm for small ranges of values where the number of elements to be sorted is roughly the same as the range of values. Pigeonhole sort is an example of a bucket sort algorithm. The pigeonhole sort algorithm works by first determining the range of values in the input sequence. This range is used to create a set of pigeonholes or buckets, each of which can hold one or more elements from the input sequence. Each element in the input sequence is then placed into its corresponding pigeonhole based on its value. If two or more elements have the same value, they can be placed in the same pigeonhole. Once all the elements have been placed into their corresponding pigeonholes, the elements are sorted within each pigeonhole. Finally, the sorted elements are combined into a single output sequence. Pigeonhole sort has a time complexity...

Sieve of Eratosthenes

The Sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to a given limit. It was devised by the Greek mathematician Eratosthenes around 200 BCE, and it is still used today in various applications, such as cryptography and computer science. The basic idea of the Sieve of Eratosthenes is to eliminate all composite numbers (i.e., non-prime numbers) in a range of numbers from 2 to some upper limit. To do this, we start by marking all the numbers from 2 to the limit as potential primes. We then iterate through the list of numbers, starting with 2, and for each prime number we encounter, we mark all its multiples as composite. This process is repeated for each subsequent prime number until we reach the end of the list. At the end of this process, all the unmarked numbers that remain are primes. This is because any composite number in the list would have been marked as a multiple of some smaller prime number, and thus eliminated from the list. For example, if we sta...