In this article binary search in c we give the information bout The binary search method can be use only with the data, which is already in the sorted order.
Binary Search in c:
Binary search is most powerful and efficient searching method. The binary search method can be use only with the data, which is already in the sorted order.
In this method, the given element that is to be search is compared with the middle element of given array.
There are three cases in this method.
- If the given element for searching is same as middle element of an array then search is successful.
- If the given element for searching is less than a middle element of an array, then searching is done only is first half of array.
- If the given element for searching is greater than a middle element of an array, then searching is done only in second half of array.
| First Half of an array | Middle element of an array | Second half of an array |
Binary Search Algorithm:
Step 1: Start
2: Read n elements of an array arr[] in sorted order Or Read n elements of an array arr[] and sort the elements.
3: Read element Y to be search
4: set beg=0 and end =n-1
5: Calculate mid = (beg + end)/ 2;
6: if Y=arr[mid] then
Display “Element is found…..search successful ” and go to step 10.
7: if Y<arr[mid] then
End=mid-1
Otherwise
beg = mid + 1
8: if beg < = end then go to step 5
9: Display “ Element not found ….., search Unsuccessful”.
10: Stop.
Binary Search Example:
Consider the elements of an array as follows
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| Value | 16 | 19 | 21 | 23 | 28 | 36 | 53 | 62 | 69 | 76 |
The element to be search is 53.
Iteration – 1:
Beg=0, end=9, mid=(0 + 9) / 2 = 4
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| Value | 16 | 19 | 21 | 23 | 28 | 36 | 53 | 62 | 69 | 76 |
As the mid is 4, therefore the middle element is 28.
Compare middle element 28 with 53.
Since 53 > 28, Search the element in the right portion of the array.
Hence, now beg = mid + 1, i.e. 4 + 1 = 5
There is no change in the value of end.
Iteration – 2:
Beg = 5, end =9, mid = ( 5 + 9 ) / 2 = 7
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| Value | 16 | 19 | 21 | 23 | 28 | 36 | 53 | 62 | 69 | 76 |
As the mid is 7, therefore the middle element is 62.
Compare middle element 62 with 53.
Since 53 < 62, search the element in the left portion of the array.
Hence, now end = mid = 7. There is no change in the value of beg.
Iteration – 3:
Beg = 5, end = 7, mid = ( 5 + 7 ) / 2 = 6
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| Value | 16 | 19 | 21 | 23 | 28 | 36 | 53 | 62 | 69 | 76 |
Here we find the index of element to be search. Now we can access the value using index. Thus, search is successful.
Binary Search Program:
void main()
{
int arr[11]={2,13,16,23,36,48,56,63,79,82,90};
int beg=0,end=10,mid=0,n=0, flag=0;
printf(“\n Enter element to be search : ”);
scanf(“%d”,&n);
while((beg<=end) && (n!=arr[mid]))
{
mid(beg+end)/2;
if(n==arr[mid])
{
printf(“\n Search is successful…”);
flag=1;
break;
}
if(n<arr[mid])
end=mid-1;
else
beg=mid+1;
}
if(flag==0)
printf(“\n Search is not successful…”);
}
O/P:
Enter element to be search : 25
Search is not successful…
Searching Applications:
- To search a particular record in database.
- To retrieve a data from storage device speedily and efficiently.
Some More:
POP- Introduction to Programming Using ‘C’
OOP – Object Oriented Programming
DBMS – Database Management System
RDBMS – Relational Database Management System
Join Now: Data Warehousing and Data Mining