Data Structures(Linear search in data structures)

-

Searching:

👉  Searching is the process of finding some particular element in the list. 

👉  If the element is present in the list, then the process is called successful and the process returns the location of that element, otherwise the search is called unsuccessful.

👉  There are two popular search methods that are widely used in order to search some item into the list. 

            🔯   Linear Search

            🔯   Binary Search

Linear Search

👉  Linear search is the simplest search algorithm and often called sequential search. 

👉  In this type of searching, we simply traverse the list completely and match each element of the list with the item whose location is to be found. 

👉  If the match found then location of the item is returned otherwise the algorithm return NULL.

👉  Linear search is mostly used to search an unordered list in which the items are not sorted.

Technique:

The steps used in the implementation of Linear Search are listed as follows -

  • First, we have to traverse the array elements using a for loop.
  • In each iteration of for loop, compare the search element with the current array element, and -
    • If the element matches, then return the index of the corresponding array element.
    • If the element does not match, then move to the next element.
  • If there is no match or the search element is not present in the given array, return -1.

Algorithm

LINEAR_SEARCH(A, N, VAL)

Step 1: [INITIALIZE] SET POS = -1

Step 2: [INITIALIZE] SET I = 1

Step 3: Repeat Step 4 while I<=N

Step 4: IF A[I] = VAL

SET POS = I

PRINT POS

Go to Step 6

[END OF IF]

SET I = I + 1

[END OF LOOP]

Step 5: IF POS = -1

PRINT " VALUE IS NOT PRESENTIN THE ARRAY "

[END OF IF]

Step 6: EXIT


Complexity of algorithm


Complexity         Best Case         Average Case         Worst Case

Time                     O(1)                 O(n)                         O(n)

Space                                                                             O(1)

Working of Linear search:

Let the elements of array are -

Linear Search Algorithm

Let the element to be searched is K = 41

Now, start from the first element and compare K with each element of the array.

Linear Search Algorithm

The value of K, i.e., 41, is not matched with the first element of the array. So, move to the next element. And follow the same process until the respective element is found.

Linear Search Algorithm

Now, the element to be searched is found. So algorithm will return the index of the element match

Implementation of Linear Search:

#include <stdio.h>

#include <conio.h>

void main()
{
  int a[10], search, i, n;

  printf("Enter number of elements in array\n");
  scanf("%d", &n);

  for (i = 0; i < n; i++)

    scanf("%d", &a[i]);

  printf("Enter a number to search\n");
  scanf("%d", &search);

  for (i = 0; i < n; i++)
  {
    if (a[i] == search)    /* If required element is found */
    {
      printf("%d is present at location %d.\n", search, i+1);
      break;
    }
  }
  if (i == n)
    printf("%d isn't present in the array.\n", search);

 
}

OUTPUT:



Comments

Post a Comment

Popular posts from this blog

String Functions in C Language(C Language)

-
  C String Functions There are many important string functions defined in "string.h" library. No. Function Description 1) strlen(string_name) returns the length of string name. 2) strcpy(destination, source) copies the contents of source string to destination string. 3) strcat(first_string, second_string) concats or joins first string with second string. The result of the string is stored in first string. 4) strcmp(first_string, second_string) compares the first string with second string. If both strings are same, it returns 0. 5) strrev(string) returns reverse string. 6) strlwr(string) returns string characters in lowercase. 7) strupr(string) returns string characters in uppercase. 8) strstr( st...
Read more

PHP Array Functions

-
  PHP  Array  Functions The array functions allow you to access and manipulate arrays. Simple and multi-dimensional arrays are supported. Function Description array() Creates an array array_column() Returns the values from a single column in the input array array_combine() Creates an array by using the elements from one "keys" array and one "values" array array_flip() Flips/Exchanges all keys with their associated values in an array array_pop() Deletes the last element of an array array_push() Inserts one or more elements to the end of an array array_replace() Replaces the values of the first array with the values from following arrays array_reverse() Returns an array in the reverse order array_search() Searches an array for a given value ...
Read more

Home Menu Options in Ms Word

-
Image
Microsoft Word Ribbon The following are the different options and tools listed in the Microsoft Word Ribbon for each of the tabs. Each section below is outlined first by the tab name, then by each section on the tab. Home tab                                    Undo Undo Typing  - Removes the last thing you typed. Repeat Typing  - If you accidentally hit undo typing, you can re-enter the previous text.                                      Clipboard Paste  - Pastes information from the  clipboard . Cut  - Removes information from the document and puts it in the clipboard. Copy  - Copies information from the document for the clipboard. Format Painter  - Applies formatting from another section of a docume...
Read more