Explain Searching?

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. However, choice of the algorithm depends upon the arrangement of 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. The algorithm of linear search is given as follows.

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)

C Program

1. #include<stdio.h>   
2. void main ()  
3. {  
4.     int a[10] = {10, 23, 40, 1, 2, 0, 14, 13, 50, 9};  
5.     int item, i,flag;  
6.     printf("\nEnter Item which is to be searched\n");  
7.     scanf("%d",&item);  
8.     for (i = 0; i< 10; i++)  
9.     {  
10.         if(a[i] == item)   
11.         {  
12.             flag = i+1;  
13.             break;  
14.         }   
15.         else   
16.         flag = 0;  
17.     }   
18.     if(flag != 0)  
19.     {  
20.         printf("\nItem found at location %d\n",flag);  
21.     }  
22.     else  
23.     {  
24.         printf("\nItem not found\n");   
25.     }  
26. }   

Output:

Enter Item which is to be searched
20
Item not found
Enter Item which is to be searched
23
Item found at location 2 

Java Program

1. import java.util.Scanner;  
2.   
3. public class Leniear_Search {  
4. public static void main(String[] args) {  
5.     int[] arr = {10, 23, 15, 8, 4, 3, 25, 30, 34, 2, 19};  
6.     int item,flag=0;   
7.     Scanner sc = new Scanner(System.in);  
8.     System.out.println("Enter Item ?");  
9.     item = sc.nextInt();  
10.     for(int i = 0; i<10; i++)  
11.     {  
12.         if(arr[i]==item)  
13.         {  
14.             flag = i+1;  
15.             break;  
16.         }  
17.         else   
18.             flag = 0;   
19.     }  
20.     if(flag != 0)  
21.     {  
22.         System.out.println("Item found at location" + flag);  
23.     }  
24.     else   
25.         System.out.println("Item not found");  
26.       
27. }  
28. }  

Output:

Enter Item ?
23
Item found at location 2
Enter Item ?
22
Item not found

C# Program

1. using System;  
2.                   
3. public class LinearSearch  
4. {  
5.     public static void Main()  
6.     {  
7.         int item, flag = 0;  
8.         int[]  a= {10, 23, 5, 90, 89, 34, 12, 34, 1, 78};   
9.         Console.WriteLine("Enter the item value");  
10.         item = Convert.ToInt32(Console.ReadLine());  
11.         for(int i=0;i<10;i++)  
12.         {  
13.             if(item == a[i])  
14.             {  
15.                 flag = i+1;  
16.                 break;  
17.             }  
18.             else   
19.                 flag = 0;   
20.         }  
21.         if(flag != 0 )   
22.         {  
23.             Console.WriteLine("Item Found at Location " + flag);  
24.         }  
25.         else   
26.             Console.WriteLine("Item Not Found");  
27.           
28.     }  
29. }  

Output:

Enter the item value
78
Item Found at Location 10

Enter the item value 
22
Item not found 

Python Program

1. arr = [10,2,3,4,23,5,21,45,90,100];  
2. item = int(input("Enter the item which you want to search "));  
3. for i in range (0,len(arr)):  
4.     if arr[i] == item:  
5.         flag = i+1;  
6.         break;  
7.     else:   
8.         flag = 0;   
9. if flag != 0:   
10.     print("Item found at location %d" % (flag));  
11. else :   
12.     print("Item not found");  

Output:

Enter the item which you want to search 2
Item found at location 2
Enter the item which you want to search 101 
Item not found