Binary Searching Using Array

Binary Searching Using Array – ये अत्‍यधिक उपयुक्त तकनीक है लेकिन इसका प्रयोग केवल Sorted List पर ही किया जा सकता है। Linear Searching की तुलना में Binary Searching बहुत Fast गति से काम करती है। माना कि-

Lowest      =    List का न्‍यूनतम मान
Highest     =    List का अधिकतम मान
Mid           =    List का मध्‍यमान

Mid           =   Lowest + Highest / 2

इस प्रक्रिया में Key के मान की List के मध्‍यमान से तुलना की जाती है। यदि मध्‍यमान Mid Key के मान से अधिक होता है तो Key के मान की तुलना List के Lowest भाग से की जाती है।

Highest = Mid – 1

तथा Mid के नए मान को वापस Mid = Lowest + Highest / 2 द्वारा प्राप्त किया जाता है। यदि Key का मान Mid के मान से अधिक होता है, तो Key के मान को List के Highest भाग में खोजा जाता है। यानी

Lowest = Mid + 1

वापस से उपरोक्त सु= द्वारा Mid का नया मान प्राप्त किया जाता है। ये क्रम तब तक चलता रहता है जब तक कि Key का मान प्राप्त ना हो जाए या List समाप्त ना हो जाए। Binary Search की Algorithm निम्नानुसार है। माना N Elements की एक Sorted List int X[N] है। यदि Key का मान List में मिल जाता है, तो उसे FOUND में Store करना है। निम्न चित्र द्वारा इसे समय ाने की कोशिश की जा रही है। जिसमें 1 को खोजा जा रहा है। यानी x = 1 है।

Array[10]
low = 0;
high = n-1; so high = 10-1 = 9
mid = 0 + 9 / 2
mid = 4

Index Number 4 पर मान 5 है इसलिए x का मान array[mid] यानी Array[4] के बराबर नहीं है।

x का मान mid से छोटा है इसलिए Key का मान Array के Lower Part में होगा। इसलिए Loop के Second Iteration में low का मान 0 ही रहेगा लेकिन high का मान Change होकर mid+1 हो जाएगा। यानी

low = 0;
high = n-1; so high = 3-1 + 1 = 4
mid = 0 + 4 / 2
mid = 2

Index Number 3 पर स्थित मान Key x के मान के बराबर नहीं है, इसलिए x के मान को वापस Check किया जाता है कि x का मान mid के मान से कम है या अधिक। चूंकि x का मान 1 है और mid मान 3 है इसलिए वापस x का मान Array के Lower Part में होगा। वापस low के मान में कोई परिवर्तन नहीं होगा लेकिन high का मान mid+1 हो जाएगा। यानी

low = 0;
high = n-1; ( mid + 1 )so high = 2-1 + 1 = 2
mid = 0 + 2 / 2
mid = 1

अगले Iteration में x का मान Array के प्रथम Element पर प्राप्त हो जाएगा। Binary Search का Algorithm हम निम्नानुसार लिख सकते हैं-

[code]
Algorithm: 
//=====================================================================
1    Let LOWEST = 0 ; HIGHEST = N; FOUND = 0; and  flag = false;
2    WHILE [ ( LOWEST = HIGHEST ) .AND. ( flag = false)]
            Perform steps 3 to 5

3    Mid      =    Lowest + Highest / 2

4    IF X[MID] = (‘A’) then [FOUND = MID; flag = true];

5    IF X[mid] < ‘A’ then LOWEST = MID – 1;
            ELSE HIGHEST = MID – 1;

6    IF ( flag = true ) then print FOUND
            ELSE ‘unsuccessful search’;

7    END
//=====================================================================
[/code]