Linear Searching using Array

Linear Searching using Array – किसी अव्‍यवस्थित List में से Searching करने की यह सबसे सरल विधि होती है। जैसे किसी Data Structure Array में हमें ये खोजना हो, कि अंक 10 उपस्थित है या नहीं। यह जानने के लिये एक Key Variable लेंगे और उस Key का मान 10 कर देंगे। फिर क्रम से इस Key के मान की तुलना Array के हर Element से करेंगे।

Array के हर Element से Key के मान की तुलना का ये क्रम तब तक चलता रहता है, जब तक कि Array के किसी Element का मान 10 प्राप्त ना हो जाए या फिर Array के सभी Elements का अंत ना हो जाए। इसका Algorithm निम्नानुसार लिख सकते हैं। माना पुर्णांक मानों का एक Array ARRAY[N] है।

[code]
Algorithm
//===================================================================
1    LET COUNT = 1; and  FOUND =0;
2    While ( COUNT < N ) DO
            If ARRAY[COUNT] =  VALUE then FOUND = COUNT
            COUNT = COUNT + 1;
3    Print FOUND
4    END
//===================================================================
[/code]

यह एक अच्छी तकनीक है, लेकिन इस तकनीक में Array के हर Element को Check करना पडता है, जिससे Program की गति कम हो जाती है। इसे निम्न चित्र में दिखाया गया है-

इस Algorithm पर आधारित एक प्रोग्राम देखते हैं, जिसमें एक Array में Store विभिन्न अंकों में से मनचाहे अंक को खोजना है, कि अमुक अंक List में उपलब्ध है या नहीं ?

[code]
//=====================================================================
#include<stdio.h>
main()
{
int j, k[10] , key, found=-1;
clrscr();

for ( j = 0; j<10; j++)
{
      printf("Enter %d digit  ", j+1);
      scanf("%d", &k[j] );
}

printf("\n Which Number Do you want to FIND ");
scanf("%d", &key);

for ( j = 0; j<10; j++)
{
      if( k[j] == key )
      found=key;
}

if(found > -1 )
      printf("\n Number is present in The List ");
if(found < 0)
      printf("\n The Number is not Present in the List ");
getch();
}
//=====================================================================

Output 1
//=====================================================================
Enter 1 digit  4
Enter 2 digit  344
Enter 3 digit  344
Enter 4 digit  34
Enter 5 digit  434
Enter 6 digit  434
Enter 7 digit  34
Enter 8 digit  555
Enter 9 digit  55
Enter 10 digit 5
Which Number Do you want to FIND 2

The Number is not Present in the List
//=====================================================================

Output 2
//=====================================================================
Enter 1 digit  1
Enter 2 digit  2
Enter 3 digit  3
Enter 4 digit  4
Enter 5 digit  5
Enter 6 digit  6
Enter 7 digit  7
Enter 8 digit  87
Enter 9 digit  89
Enter 10 digit  9
Which Number Do you want to FIND 9

Number is present in The List
//=====================================================================
[/code]

इस प्रोग्राम में Linear Searching की गई है। सबसे पहले एक Array में मानों को Input किया गया है। फिर एक Key नाम के Variable में वो अंक लेते हैं जिसे List में खोजना है। इस अंक को Loop द्वारा Array के हर Element से Check किया जाता है। यदि key का अंक Array में प्राप्त होता है तो if condition सत्‍य हो जाती है और Found नाम के Variable में key का अंक प्राप्त हो जाता है। यदि key का अंक list में प्राप्त नहीं होता है, तो found का मान -1 जो कि found को Declare करते समय ही दे दिया गया था, रहता है।

यदि List में key का मान मिल जाता है तो found का मान -1 से अधिक रहता है और Output में Massage मिलता है कि List मे अंक उपलब्ध है। यदि List में अंक उपलब्ध नहीं होता है तो found का मान -1 होने के कारण 0 से छोटा रहता है। इसलिये Output में Massage प्राप्त होता है कि जो अंक खोजा जा रहा है वह अंक List में उपलब्ध नहीं है। इस प्रकार से Linear Searching की जाती है।

Linear Search Algorithm की Complexity को भी हम f(n) Function का प्रयोग करके पता कर सकते हैं। यदि किसी Linear Data Structure में n Data हों तो उस Data Structure से किसी ITEM को Find करने के लिए Worst Case Algorithm में हमें अधिकतम n+1 बार Comparisons करने होंगे जबकि यदि Data ITEM Data Structure के अन्त में हो या ITEM Data Structure में ना हो। जबकि Average Case Algorithm में ITEM के प्राप्त होने की सम्भावना n+1/2 होती है। (Linear Searching using Array in Hindi)