Learn Searching Algorithms in Data Structure with Simple Example

Searching Algorithms in Data Structure: जिस प्रकार से किसी Telephone Directory में किसी नाम से Telephone Number खोजते हैं या किसी Telephone Number से नाम खोजते हैं, या किसी Student के Roll Number द्वारा Student का Record खोजा जाता है, ठीक इसी प्रकार से एक Key द्वारा किसी भी Data Structure से उस Key से सम्बंधित सारी जानकारी प्राप्त की जा सकती है।

जैसे यदि हमें Telephone Directory से 223344 Number किस व्यक्ति का है और वह व्यक्ति कहां रहता है, ये जानना हो, तो हम इस Number को Telephone Directory के हर Number से Compare करते हैं, और जहां ये Comparison एकदम मेल करती है, सम्बंधित व्यक्ति का नाम पता आदि हम जान लेते हैं।

इस प्रकार से ये Telephone Number एक Key के रूप में Use किया जाता है, जो बाकी की सम्बंधित जानकारी दे देता है। यही प्रक्रिया हम Data Structure के साथ भी करते हैं। Computer में Searching दो प्रकार की होती है-

Internal Search

जब सभी Records Computer की Main Memory में होते हैं, तो Main Memory से की जाने वाली Searching Internal Search कहलाती है।

External Search

जब Records बडे होते हैं व Records की संख्‍या अधिक होती है, तब Records को Hard disk पर संग्रहित कर लिया जाता है। फिर इस Hard Disk से Searching की जाती है। इस Searching को External Searching कहा जाता है। Internal Searching के भी दो भाग हैं।

Linear Searching

किसी अव्यवस्थित 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] है।

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

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

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

#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 2t
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

इस प्रोग्राम में 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 होती है। (Searching Algorithms in Data Structure)