Binary Search or half-interval search or logarithmic search or binary chop Introduction and function / algorithm / program

Binary / half-interval search:- 

"Binary Search is applied on the sorted list or array data structure. It compares the given item to the middle element of the array. Binary Search is also called half-interval search or logarithmic search or binary chop."

"बाइनरी सर्च को बढ़ते या घटते हुए क्रम में व्यवस्थित लिस्ट या अरे डाटा स्ट्रक्चर पर लागु किया जाता है। यहाँ दिए गए आइटम की तुलना अरे के मिडिल एलिमेंट से की जाती है। बाइनरी सर्च को हाफ-इन्टरवल सर्च या लोगरिथमीक सर्च या बाइनरी चोप के नाम से भी जाना जाता है।"

In binary search, we first get lower bound(lb) and upper bound(ub) of given list or array and calculate mid  i.e. mid=(lb+ub)/2. 

After that we compare the item with the element in the middle position of the list or array i.e.list[mid]. 

If the element is matched, then we return the location or position of that element. otherwise

If item<list[mid], then item must be exist in the lower half of the list or array so we set ub=mid-1.
If item>list[mid], then item must be exist in the upper half of the list or array so we set lb=mid+1.
This procedure will continue on the lower/upper half of the list or array until lb<=ub whenever the  lb>ub then binary search is called unsuccessful. 

Binary Search is more efficient than Linear Search and it is very useful for searching a list with large number of elements. Its worst/average case time complexity is O(log n) and space complexity is O(1).

बाइनरी सर्च में, हम सबसे पहले अरे की निम्न सीमा(lb) एवं उच्च सीमा(ub) प्राप्त करते है एवं mid=(lb+ub)/2 की गणना करते है।

इसके पश्चात् आइटम की तुलना, अरे के मिडिल एलिमेंट list[mid] से करते है। यदि यह आइटम के बराबर है तब इस एलिमेंट की पोजीशन या लोकेशन प्रदान की जाती है। अन्यथा 

यदि  item<list[mid], अर्थात आइटम ज़रूर लिस्ट के पहले भाग में होगा तब ub=mid-1 सेट किया जाता है। 

यदि  item>list[mid], अर्थात आइटम ज़रूर लिस्ट के दुसरे भाग में होगा तब lb=mid+1 सेट किया जाता है।

यह प्रक्रिया लिस्ट के पहले या दुसरे भाग पर तब तक चलती रहती है जब तक कि lb<=ub होता है। जैसे ही lb>ub तब बाइनरी सर्च को असफल माना जाता है। 

बाइनरी सर्च लीनियर सर्च की तुलना में अधिक प्रभावी युक्ति है। यह अधिक संख्या में एलिमेंट रखने वाली लिस्ट / अरे पर लागु की जा सकती है।

बाइनरी सर्च की वर्स्ट / एवरेज केस टाइम कॉम्प्लेक्सिटी O(log n) एवं स्पेस कॉम्प्लेक्सिटी O(1) होती है।    

Binary Search function / algorithm / program :-

File Name:- bs.cpp

#include<iostream.h>

#include<conio.h>

#define N 5

void bs(){

int list[N],item,i,lb=0,ub=N-1,mid;

cout<<"Enter Elements of List"<<endl;

for(i=0;i<N;i++){

cout<<"Enter "<<i+1<<" element=";

cin>>list[i];

}

cout<<"Enter an Item to search=";

cin>>item;

while(lb<=ub){

mid=(lb+ub)/2;

if(item==list[mid]){

cout<<item<<" is found at "<<mid<<"th index and "<<mid+1<<"th position"<<endl;

return;

}

else{

if(item>list[mid]) lb=mid+1;

else ub=mid-1;

}}

cout<<item<<" is not found"<<endl<<"Search Unsuccessful"<<endl;

return;

}

void main(){

clrscr();

cout<<"Binary Search"<<endl;

bs();

getch();

}

File Name:- bs.c

#include<stdio.h>

#include<conio.h>

#define N 5

void bs(){

int list[N],item,i,lb=0,ub=N-1,mid;

printf("Enter Elements of List\n");

for(i=0;i<N;i++){

printf("Enter %d element=",i+1);

scanf("%d",&list[i]);

}

printf("Enter an Item to search=");

scanf("%d",&item);

while(lb<=ub){

mid=(lb+ub)/2;

if(item==list[mid]){

printf("%d is found at %d index and %d position\n",item,mid,mid+1);

return;

}

else{

if(item>list[mid]) lb=mid+1;

else

ub=mid-1;

}

}

printf("%d is not found\n Search Unsuccessful\n",item);

return;

}

void main(){

clrscr();

printf("Binary Search\n");

bs();

getch();

}