Binary Search Tree Coding

Linear Search

Linear Search - searching and sorting - algorithm -A simple approach is to do linear search, Start from the leftmost element of arr[] and one by one compare

Problem: Given an array arr[] of n elements, write a function to search a given element x in arr[].

A simple approach is to do linear search, i.e

  • Start from the leftmost element of arr[] and one by one compare x with each element of arr[]
  • If x matches with an element, return the index.
  • If x doesn’t match with any of elements, return -1.

Example:

Linear Search

C and C++

C and C++
// Linearly search x in arr[].  If x is present then return its 
// location,  otherwise return -1
int search(int arr[], int n, int x)
{
    int i;
    for (i=0; i<n; i++)
        if (arr[i] == x)
         return i;
    return -1;
}

Python

Python
# Searching an element in a list/array in python
# can be simply done using 'in' operator
# Example:
# if x in arr:
#   print arr.index(x)
 
# If you want to implement Linear Search in python
 
# Linearly search x in arr[]
# If x is present then return its location
# else return -1
 
def search(arr, x):
 
    for i in range(len(arr)):
 
        if arr[i] == x:
            return i
 
    return -1

Java

Java
class LinearSearch
{
    // This function returns index of element x in arr[]
    static int search(int arr[], int n, int x)
    {
        for (int i = 0; i < n; i++)
        {
            // Return the index of the element if the element
            // is found
            if (arr[i] == x)
                return i;
        }
  
        // return -1 if the element is not found
        return -1;
    }
} 

The time complexity of above algorithm is O(n).

Linear search is rarely used practically because other search algorithms such as the binary search algorithm and hash tables allow significantly faster searching comparison to Linear search.

READ  C Algorithm - Reverse a String using Stack
Tags

About the author

Venkatesan Prabu

Venkatesan Prabu

Wikitechy Founder, Author, International Speaker, and Job Consultant. My role as the CEO of Wikitechy, I help businesses build their next generation digital platforms and help with their product innovation and growth strategy. I'm a frequent speaker at tech conferences and events.

Add Comment

Click here to post a comment