Linear Search

Posted by Anoop Nair on September 4, 2017 Tags: Java C Data Structures Searching

What is Searching ?

In Data Structures searching refers to finding the location of a data element or printing some message if data element is not found.
Linear search is the simplest meathod of searching a data element ITEM in a linear array ARR[ ]. It follows the simple method of comparing each value of the ARR[ ] to ITEM, if the value is found the search is successful and we get the index value of the location else a message " Element not found" is displayed.

Complexity of Linear Search

Best Case Its when we get the ITEM at ARR[1] so complexity is O(1) .

Average case The average number of comparisons required to find the ITEM in ARR[ ] is equal to half the number of element in array. So it depends on the no. of elements n hence the complexity O(n).

Worst Case The worst case when we have to search the entire array so the complexity is O(n) here n is the size of array

Linear Search Program In C

    
      void main(){
          int arr[20], value , i,index = 0, n, count;
          printf("Enter the size of array \n");
          scanf("%d", &n);

          // getting user input for array

          printf("Enter the values of array \n");
          for(i=0; i< n ; i++){
              scanf("%d", &arr[i]);
          }
          printf("Enter the value to be searched in array");
          scanf("%d", &value);

          // comparing each element of array with the value we want to search

          for(i=0 ; i< n ; i++){
              if(arr[i] == value){
                 count = 1 ;
                  index = i;
                 break;
              }
              else{
                  count = 0;
              }
          }
          if(count == 0){
              printf("Element Not Found");
          }
          else{
              printf("Element Found At index \t %d" , index);
          }
      }
    
  

Output

output


Linear Search Program In Java

    
      package basics;
      import java.io.* ;
      public class LinearSearch {
          public static void main(String arg[]) throws IOException{
              int i, n , value;
              int flag = 0 , index = 0;
              BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
              int arr[] = new int[20];
              System.out.println("Enter the size of array");
              n = Integer.parseInt(br.readLine());

              System.out.println("Enter the Values of the array");
              for(i=0 ; i< n ; i++){
                  arr[i] = Integer.parseInt(br.readLine());

              }
              System.out.println("Enter the value to be searched in array");
              value = Integer.parseInt(br.readLine());

              for(i=0 ; i< n ; i++){
                  if(arr[i] == value ){
                      flag = 1;
                      index = i;
                      break;
                  }
                  else flag = 0 ;
              }
              if(flag == 1){
                  System.out.println("The value is present in Array and is at index \t" + index);
              }
              else{
                   System.out.println("The value is not found in Array" );
              }
          }

      }
    
  

Output

output

Follow the following links to learn more



COMMENTS