Linear Search

Linear search, also known as sequential search, is a simple searching algorithm that searches for a target element in a list or array one element at a time, starting from the beginning and moving sequentially through the list until the element is found or the end of the list is reached. Here's a detailed algorithm for linear search, along with a real-time example:

1.Linear Search Algorithm:Start from the first element (index 0) of the list.
2.Compare the current element with the target element you are searching for.
3.If the current element is equal to the target element, you have found a match, and you can return the index of the current element as the result.
4.If the current element is not equal to the target element and you have not reached the end of the list, move to the next element (increment the index by 1) and repeat steps 2-3.
5.If you have reached the end of the list (i.e., you have compared all elements) and have not found a match, return a "not found" or "element not in the list" indicator.

Real-Time Example:

Let's say you have an array of integers and you want to search for the number 7 in this array using linear search.

Array: [12, 34, 5, 2, 7, 8, 19, 42]

1.Let's implement the linear search algorithm step by step:Start at index 0, which is the first element: 12.
2.Compare 12 with the target element (7). They are not equal.
3.Move to the next element at index 1: 34.
4.Compare 34 with 7. They are not equal.
5.Continue this process until you reach index 4, where the element is 7. You have found a match!
6.Return the index 4 as the result.

In this example, linear search successfully found the target element (7) at index 4. If the target element was not in the list, you would continue searching until you reach the end of the list and return a "not found" indicator.

Pseudo code
function linear_search(array, target):
    for each element in array:
        if element equals target:
            return index of element
    return -1  // Target not found in the array

In this pseudocode:
array represents the list or array in which you want to search.
target represents the element you are looking for.
The for each element in array loop iterates through each element of the array.
Inside the loop, it checks if the current element is equal to the target.
If a match is found, it returns the index of the element.
If the loop completes without finding a match, it returns -1 to indicate that the target element is not in the array.

Let's analyze the time and space complexity of the linear search algorithm:

Time Complexity: The time complexity of the linear search algorithm is O(n), where "n" is the number of elements in the array. This is because, in the worst case, you may have to traverse the entire array to find the target element. In the best-case scenario, where the target element is found at the beginning of the array, the time complexity is O(1), but we typically consider the worst-case time complexity.

Space Complexity:

The space complexity of the linear search algorithm is O(1), which means it uses a constant amount of additional memory regardless of the size of the input array. This is because the algorithm does not require any additional data structures or memory allocation that depend on the size of the input.

In summary:
Time Complexity: O(n) in the worst case, O(1) in the best case.
Space Complexity: O(1).


C program - Linear Search
/*******************************************************************************/
#include <stdio.h>
int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i; // Return the index of the target element if found
        }
    }
    return -1; // Return -1 if the target element is not found
}
int main()
{
int arr[100];
int n, i, target, result;
/*
* Read size of array and elements in array
*/
printf("Enter size of array :: ");
scanf("%d", &n);

printf("\nEnter elements in array: \n");
for(i=0; i<n; i++)
{
printf("Enter %d element in array :: ",i+1);
scanf("%d", &arr[i]);
}

printf("\nEnter the element to search within the array: ");
scanf("%d", &target);

/* call the linear search function */
result = linearSearch(arr, n, target);

if (result != -1) {
        printf("Element %d found at index %d.\n", target, result);
    } else {
        printf("Element %d not found in the list.\n", target);
    }

return 0;
}

Comments

Post a Comment

Popular posts from this blog

Data Structures CST 201 KTU Third Semester Syllabus Notes and Solved Questions- Dr Binu V P 984739060

Dr BinuV P -About Me About The Course Syllabus Data Structures Lab CSL 201 ( Do the Programs to Understand the Concept Well) Model Question Paper CST 201 Data Structures University Question Papers CST 201 Data Structures Module-1 Basic Concepts of Data Structures 1.1 System Life Cycle 1.2 Algorithms , Performance Analysis  1.3 Space Complexity, Time Complexity  1.4 Asymptotic Analysis and Notations  1.5 Complexity Calculation of Simple Algorithms Module-2 Arrays and Searching  2.1 Polynomial representation using Arrays  2.2 Sparse matrix  2.3 Stacks  2.4 Queues 2.5 Circular Queues  2.6 Priority Queues 2.7 Double Ended Queues 2.8 Infix to  Postfix Conversion  2.9  Evaluation of Postfix Expression 2.10 Linear Search  2.11 Binary Search Module-3 Linked List and Memory Management 3.1 Linked List -Self Referential Structures  3.2 Dynamic Memory Allocation  3.3 Singly Linked List-Operations on Linked List 3.4 Doubly Linked List 3.5 Circular Linked List  3.6 Stack using Linked List  3.7 Queue
Read more

Stack

Image
A stack is a fundamental data structure in computer science and programming that follows the Last-In, First-Out (LIFO) principle . It is named "stack" because it resembles a stack of items, like a stack of plates or books, where you can only add or remove items from the top. Stacks are used for various purposes in programming and are essential in many algorithms and applications. Let's delve into the details of stacks: Key Operations:  A stack typically supports two primary operations: Push: This operation adds an element to the top of the stack. It is analogous to placing an item on top of the stack. Pop: This operation removes and returns the top element of the stack. It is like taking the top item off the stack. Additionally, stacks often provide the following operations: Peek (or Top): This operation retrieves the top element without removing it. It allows you to examine the top item without modifying the stack. IsEmpty: This operation checks if the stack is empty.
Read more

Quick Sort

Quick sort is a popular sorting algorithm that uses a divide-and-conquer strategy to efficiently sort an array or list. It works by selecting a "pivot" element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then recursively sorted. Here's a detailed algorithm for the Quick Sort algorithm: Algorithm: Quick Sort 1.Choose a pivot element from the array. This can be done in various ways, such as selecting the first element, the last element, or a random element. The choice of the pivot can affect the algorithm's performance. 2,Partition the array into two sub-arrays:     Elements less than the pivot (left sub-array).     Elements greater than the pivot (right sub-array). 3.Recursively apply the Quick Sort algorithm to the left and right sub-arrays. 4.Combine the sorted left sub-array, pivot, and sorted right sub-array to obtain the final sorted ar
Read more