Linear Search

 

Linear Search

Linear Search is defined as a sequential search algorithm that starts at one end and goes through each element of a list until the desired element is found, otherwise the search continues till the end of the data set. It is the easiest searching algorithm.

Linear Search Algorithm

Step 1: First, read the search element (Target element) in the array.

Step 2: In the second step compare the search element with the first element in the array.

Step 3: If both are matched, display “Target element is found” and terminate the Linear Search 

function.

Step 4: If both are not matched, compare the search element with the next element in the array.

Step 5: In this step, repeat steps 3 and 4 until the search (Target) element is compared with the 

last element of the array.

Step 6 – If the last element in the list does not match, the Linear Search Function will be 

terminated, and the message “Element is not found” will be displayed.

Follow the given steps to solve the problem:

1. Set the first element of the array as the current element.
2. If the current element is the target element, return its index.
3. If the current element is not the target element and if there are more elements in the array, set the current element to the next element and repeat step 2.
4. If the current element is not the target element and there are no more elements in the array, return -1 to indicate that the element was not found.

Example:

Given an array arr[] of N elements,

the task is to write a function to search a given element x in arr[].


Solution:

class LinearSearch { public static int search(int arr[], int x) { int N = arr.length; for (int i = 0; i < N; i++) { if (arr[i] == x) return i; } return -1; } // Driver's code public static void main(String args[]) { int arr[] = { 2, 3, 4, 10, 40 }; int x = 10; // Function call int result = search(arr, x); if (result == -1) System.out.print( "Element is not present in array"); else System.out.print("Element is present at index " + result); } } Output: Element is present at index 3 Time complexity: O(N) Auxiliary Space: O(1)




Linear search Recursive approach:




Follow the given steps to solve the problem:

• If the size of the array is zero then, return -1, representing that the element is not found. This can also be treated as the base condition of a recursion call.
• Otherwise, check if the element at the current index in the array is equal to the key or not i.e, arr[size – 1] == key
• If equal, then return the index of the found key

Below is the implementation of the above approach:

// Java Recursive Code For Linear Search

import java.io.*;

 

class Test {

    static int arr[] = { 5, 15, 6, 9, 4 };

 

    // Recursive Method to search key in the array

    static int linearsearch(int arr[], int size, int key)

    {

        if (size == 0) {

            return -1;

        }

        else if (arr[size - 1] == key) {

            // Return the index of found key.

            return size - 1;

        }

        else {

            return linearsearch(arr, size - 1, key);

        }

    }

 

    // Driver method

    public static void main(String[] args)

    {

        int key = 4;

 

        // Function call to find key

        int index = linearsearch(arr, arr.length, key);

        if (index != -1)

            System.out.println(

                "The element " + key + " is found at "

                + index + " index of the given array.");

 

        else

            System.out.println("The element " + key

                               + " is not found.");

    }

}

Output

The element 4 is found at 4 index of the given array.

Time Complexity: O(N)

Auxiliary Space: O(N)

Advantages of Linear Search:

• Linear search is simple to implement and easy to understand.
• Linear search can be used irrespective of whether the array is sorted or not. It can be used on arrays of any data type.
• Does not require any additional memory.
• It is a well suited algorithm for small datasets.

Drawbacks of Linear Search:

• Linear search has a time complexity of O(n), which in turn makes it slow for large datasets.
• Not suitable for large array.
• Linear search can be less efficient than other algorithms, such as hash tables.

When to use Linear Search:

• When we are dealing with a small dataset.
• When you need to find an exact value.
• When you are searching a dataset stored in contiguous memory.
• When you want to implement a simple algorithm.

Searching Algorithms

Searching algorithms are used to find a specific element in an array, string, linked list or some other data structure.

The most common searching algorithms are:

Linear Search : In this searching algorithm, we check the element iteratively from one end to the other.

Binary Search : In this type of the searching algorithm, we break the data structure into two equal parts and try to decide in which half we need to find for the elements.

Ternary Search : In this case, the array is divided into three parts and based on the values at partitioning positions we decide the segment where we need to find the required element.

Besides these, there are other searching algorithms like

• Jump Search
• Interpolation Search 
• Exponential Search

Array

What is Array?

An array is a collection of items of the same variable type that are stored at contiguous memory locations. It is one of the most popular and simple data structures and often used to implement other data structures. Each item in array is indexed starting with 0.

Representation Of Array

The representation of an array can be defined by its declaration. A declaration means allocating memory for an array of a given size.

There are 2 types of Array:

1. Static Array
2. Dynamic Array

1. Static Array:

Static Arrays are arrays that are declared before runtime and are assigned values while writing the code. It allocates memory at compile-time whose size is fixed. We cannot alter the static array.

Example: int arr[] = { 1, 3, 4 }; // static integer array  

Advantages of Static Array

• It has efficient execution time.
• The lifetime of static allocation is the entire run time of the program.

Disadvantages of Static Array

• In case more static data space is declared than needed, there is waste of space.
• In case less static space is declared than needed, then it becomes impossible to expand this fixed size during run time.

Dynamic Array

If we want an array to be sized based on input from the user. In such a case, dynamic arrays allow us to specify the size of an array at run-time.

Example: int* arr = new int[3]; // dynamic integer array  

The dynamic array is a variable size list data structure. It grows automatically when we try to insert an element if there is no more space left for the new element. It allows us to add and remove elements. It allocates memory at run time using the heap. It can change its size during run time.

Learn Data Structures

 Below are the most highly used Data Structures

1. Array

2. String

3. Linked List

4. Matrix/Grid

5. Stack

6. Queue

7. Heap

8. Hash

9. Tree Data Structure

10. Graph Data Structure

11. Trie Data Structure

Learn about Complexities

Learn about Complexities
The primary motive to use DSA is to solve a problem effectively and efficiently. How can you decide if a program written by you is efficient or not? This is measured by complexities. 

Complexity is of two types:
Time Complexity: Time complexity is used to measure the amount of time required to execute the code.
Space Complexity: Space complexity means the amount of space required to execute successfully the functionalities of the code. 

The time required for executing a code depends on several factors, such as: 

• The number of operations performed in the program, 
• The speed of the device, and also 
• The speed of data transfer if being executed on an online platform. 

So how can we determine which one is efficient? The answer is the use of asymptotic notation. 

The following 3 asymptotic notations are mostly used to represent the time complexity of algorithms:

Big-O Notation (Ο) – Big-O notation specifically describes the worst-case scenario.
Omega Notation (Ω) – Omega(Ω) notation specifically describes the best-case scenario.
Theta Notation (θ) – This notation represents the average complexity of an algorithm.

The most used notation in the analysis of a code is the Big O Notation which gives an upper bound of the running time of the code (or the amount of memory used in terms of input size)

Below are the running Time complexity in terms of Big-O O(f(n))

O(n!) : Worst

O(nlogn) : Bad

O(n) : Fair

O(logn) : Good

O(1) : Best

Learn Algorithms

 Below are the most commonly used Algorithms:

1. Searching Algorithm

2. Sorting Algorithm

3. Divide and Conquer Algorithm

4. Greedy Algorithm

5. Recursion

6. Backtracking Algorithm

7. Dynamic Programing

8. Pattern Searching

9. Mathematical Algorithm

10. Geometric Algorithm

11. Bitwise Algorithm

12. Randomized Algorithm

13. Batch and Bound Algorithm

Data Structure and Algorithm

What is DSA?
The term DSA stands for Data Structures and Algorithms. As the name itself suggests, it is a combination of two separate yet interrelated topics – Data Structure and Algorithms.

What is Data Structure?

A data structure is defined as a particular way of storing and organizing data in our devices to use the data efficiently and effectively. The main idea behind using data structures is to minimize the time and space complexities. An efficient data structure takes minimum memory space and requires minimum time to execute the data.

What is Algorithm?

Algorithm is defined as a process or set of well-defined instructions that are typically used to solve a particular group of problems or perform a specific type of calculation. To explain in simpler terms, it is a set of operations performed in a step-by-step manner to execute a task.

How to start learning DSA?
The complete process to learn DSA from scratch can be broken into 4 parts:

1) Learn about Time and Space complexities

2) Learn the basics of individual DataStructures 

3) Learn the basics of Algorithms