Searching It means to find the location of an item/element/value in an array/list. It will return or print the location of the item , if the item is present in the list/array, otherwise it will print “Not Found” or return a non valid index (say -1)
Binary Search It searches the element in the list by comparing it with the middle element of the list. If it is found, stop searching. Otherwise our list is reduced to half i.e left half or right half, and we will apply the same process to the list again.
Algorithm for Binary Search
binary_search(a,n,item) where item is to be found in the array a having n elements.
- beg = 0;
- end = n – 1;
- while (beg <= end)
- {
- mid = (beg + end) / 2;
- if (a[mid] == item)
- {
- printf(“Item found at location %d in the list”, mid + 1);
- break;
- }
- else if (a[mid] > item)
- end = mid – 1;
- else
- beg = mid + 1;
- }
- if (beg > end)
- printf(“Item not found in the list”);
Program for Binary Search (Without Function)
#include <stdio.h>
int main()
{
printf("***************************************************************");
printf("\n***************************************************************");
printf("\n** WAP to find an item in an array using binary search **");
printf("\n** Created by Sheetal Garg **");
printf("\n** Assistant Professor **");
printf("\n** Phone No:9467863365 **");
printf("\n***************************************************************");
printf("\n***************************************************************\n");
int n, i, beg, item, mid, end, a[50];
printf("enter no. of array elements\n");
scanf("%d", &n);
printf("enter array elements in sorted/ascending order");
for (i = 0; i < n; i++)
scanf("%d", &a[i]);
printf("enter item to find");
scanf("%d", &item);
beg = 0;
end = n - 1;
while (beg <= end)
{
mid = (beg + end) / 2;
if (a[mid] == item)
{
printf("Item found at location %d in the list", mid + 1);
break;
}
else if (a[mid] > item)
end = mid - 1;
else
beg = mid + 1;
}
if (beg > end)
printf("Item not found in the list");
return 0;
}
Output 1:
*************************************************************************** *************************************************************************** ** WAP to find location of an item in an array using binary search ** ** Created by Sheetal Garg ** ** Assistant Professor ** ** Phone No:9467863365 ** *************************************************************************** *************************************************************************** enter no. of array elements 8 enter array elements in sorted/ascending order 12 23 34 45 56 67 78 89 enter item to find 34 Item found at location 3 in the list
Output 2:
*************************************************************************** *************************************************************************** ** WAP to find location of an item in an array using binary search ** ** Created by Sheetal Garg ** ** Assistant Professor ** ** Phone No:9467863365 ** *************************************************************************** *************************************************************************** enter no. of array elements 8 enter array elements in sorted/ascending order 12 23 34 45 56 67 78 89 enter item to find 43 Item not found in the list
Program for Binary Search (With Function)
#include <stdio.h>
int binarysearch(int a[], int n, int item);
int main()
{
printf("***************************************************************");
printf("\n***************************************************************");
printf("\n** WAP to find an item in an array using binary search **");
printf("\n** Created by Sheetal Garg **");
printf("\n** Assistant Professor **");
printf("\n** Phone No:9467863365 **");
printf("\n***************************************************************");
printf("\n***************************************************************\n");
int n, i, item, a[50], loc;
printf("enter no. of array elements\n");
scanf("%d", &n);
printf("enter array elements in sorted/ascending order");
for (i = 0; i < n; i++)
scanf("%d", &a[i]);
printf("enter item to find");
scanf("%d", &item);
loc = binarysearch(a, n, item);
if (loc == 0)
printf("Item not found in the list");
else
printf("Item found at location %d in the list", loc);
return 0;
}
int binarysearch(int a[], int n, int item)
{
int beg=0,end=n-1,mid;
while(beg<=end)
{
mid = (beg + end) / 2;
if (a[mid] == item)
return mid+1;
else if (a[mid] > item)
end=mid-1;
else
beg=mid+1;
}
if(beg>end)
return 0;
}
Output 1:
*************************************************************** ** WAP to find an item in an array using binary search ** ** Created by Sheetal Garg ** ** Assistant Professor ** ** Phone No:9467863365 ** *************************************************************** *************************************************************** enter no. of array elements 5 enter array elements in sorted/ascending order 12 23 34 45 56 enter item to find34 Item found at location 3 in the list
Output 2:
*************************************************************************** *************************************************************************** ** WAP to find location of an item in an array using binary search ** ** Created by Sheetal Garg ** ** Assistant Professor ** ** Phone No:9467863365 ** *************************************************************************** *************************************************************************** enter no. of array elements 8 enter array elements in sorted/ascending order 12 23 34 45 56 67 78 89 enter item to find 43 Item not found in the list
Program for Binary Search (With Recursive Function)
#include <stdio.h>
int binarysearch(int a[], int beg, int end, int item);
int main()
{
printf("***************************************************************");
printf("\n***************************************************************");
printf("\n** WAP to find an item in an array using binary search **");
printf("\n** Created by Sheetal Garg **");
printf("\n** Assistant Professor **");
printf("\n** Phone No:9467863365 **");
printf("\n***************************************************************");
printf("\n***************************************************************\n");
int n, i, item, a[50], loc;
printf("enter no. of array elements\n");
scanf("%d", &n);
printf("enter array elements in sorted/ascending order");
for (i = 0; i < n; i++)
scanf("%d", &a[i]);
printf("enter item to find");
scanf("%d", &item);
loc = binarysearch(a, 0, n, item);
if (loc == 0)
printf("Item not found in the list");
else
printf("Item found at location %d in the list", loc);
return 0;
}
int binarysearch(int a[], int beg, int end, int item)
{
int mid;
if(beg>end)
return 0;
else
{
mid = (beg + end) / 2;
if (a[mid] == item)
return mid+1;
else if (a[mid] > item)
binarysearch(a,beg,mid-1,item);
else
binarysearch(a,mid+1,end,item);
}
}
Output 1:
** WAP to find an item in an array using binary search ** ** Created by Sheetal Garg ** ** Assistant Professor ** ** Phone No:9467863365 ** *************************************************************** *************************************************************** enter no. of array elements 6 enter array elements in sorted/ascending order 12 23 34 45 56 78 enter item to find78 Item found at location 6 in the list
Output 2:
*************************************************************************** *************************************************************************** ** WAP to find location of an item in an array using binary search ** ** Created by Sheetal Garg ** ** Assistant Professor ** ** Phone No:9467863365 ** *************************************************************************** *************************************************************************** enter no. of array elements 8 enter array elements in sorted/ascending order 12 23 34 45 56 67 78 89 enter item to find 43 Item not found in the list