Searching in Sorted Linked List

Searching in Sorted Linked List – जिस LIST में से Data Item की Location को Search किया जा रहा है वह LIST यदि SORTED हो तो हम निम्न Algorithm का प्रयोग करके Find की जाने वाली ITEM की LOCATION का पता लगा सकते हैं।

इस Algorithm में भी हमें LIST के हर Node को ITEM से Test करना पडता है। यानी इस Algorithm की Complexity व पिछले Algorithm की Complexity समान होती है।

यानी यदि हम किसी Linked List पर Binary Search Algorithm का प्रयोग करके किसी Data की LOCATION प्राप्त करना चाहें तो हम ऐसा नहीं कर सकते हैं। एक Linked List की Binary Searching नहीं की जा सकती है।

SORTED SEARCH Algorithm

[code]
SORTED_SEARCH(LIST, LINK, INFO, ITEM, LOC)

SET PTR = START
REPEAT Step 3 WHILE PTR <> NULL
IF ITEM < PTR[INFO] then
   SET PTR = PTR[LINK]            [ Now PTR points to next NODE ]
   ELSEIF ITEM = PTR[INFO] then
       SET LOCATION = PTR and EXIT   [ Search is Successful ]
   ELSE
       SET LOCATION = NULL and EXIT [ ITEM not Exists in LIST ]
EXIT
[/code]

इस Algorithm का प्रयोग करके हम निम्नानुसार एक Function Create कर सकते हैें&

SORTED SEARCH Function

[code]
void SEARCH2(struct LIST **PTR, int ITEM)
{
   struct LIST *temp;
   int LOCATION=0 ;
   temp = *PTR;
   clrscr();
   while(temp != NULL)
   {
     LOCATION++;
     if(ITEM < temp->INFO)
         temp = temp->LINK;
     else if(temp->INFO == ITEM)
     {
     printf("\nSearched Data Element Found at the %d LOCATION \n", LOCATION);
         getch();
         clrscr();
         return ;
      }
      else
      {
         printf("\nData Item Not Found In The LIST \n");
         getch();
         clrscr();
         return ;
      }
   }
   getch();
   clrscr();
}
[/code]