Binary Search In An Array Algorithm And C Code - Coding Bot

# Binary Search In An Array Algorithm And C Code

As I have already described what are Arrays and their basic creation C code, in this post, we'll learn how to perform Binary Search In An Array, its Algorithm And C Code.

In computer science, a binary search or half-interval search algorithm finds the position of a specified value (the input "key") within a sorted array. In each step, the algorithm compares the input key value with the key value of the middle element of the array. If the keys match, then a matching element has been found so its index, or position, is returned. Otherwise, if the sought key is less than the middle element's key, then the algorithm repeats its action on the sub-array to the left of the middle element or, if the input key is greater, on the sub-array to the right. If the remaining array to be searched is reduced to zero, then the key cannot be found in the array and a special "Not found" indication is returned.
A binary search halves the number of items to check with each iteration, so locating an item (or determining its absence) takes logarithmic time. A binary search is a dichotomic divide and conquer search algorithm.

### Recursive Algorithm

A straightforward implementation of binary search is recursive. The initial call uses the indices of the entire array to be searched. The procedure then calculates an index midway between the two indices, determines which of the two subarrays to search, and then does a recursive call to search that subarray.

Each of the calls is tail recursive, so a compiler need not make a new stack frame for each call. The variables `imin` and `imax` are the lowest and highest inclusive indices that are searched.
```int binary_search(int A[], int key, int imin, int imax)
{
// test if array is empty
if (imax < imin):
return KEY_NOT_FOUND;
else
{
// calculate midpoint to cut set in half
int imid = midpoint(imin, imax);

// three-way comparison
if (A[imid] > key)
// key is in lower subset
return binary_search(A, key, imin, imid-1);
else if (A[imid] < key)
// key is in upper subset
return binary_search(A, key, imid+1, imax);
else
// key has been found
return imid;
}
}
```
```
```
It is invoked with initial `imin` and `imax` values of `0` and `N-1` for a zero based array.
The number type "int" shown in the code has an influence on how the midpoint calculation can be implemented correctly. With unlimited numbers, the midpoint can be calculated as `"(imin + imax) / 2"`

### C Code For Binary Search:

```/* Double-Click To Select Code */

#include<stdio.h>
#include<conio.h>
void main()
{
int arr[10], num, i, n, found=0, pos=-1, beg, end, mid;
clrscr();

printf("Enter the number of elements in the array: ");
scanf("%d",&n);
printf("\nEnter the elements: \n");
for(i=0 ; i < n ; i++)
{
printf("arr[%d] = ",i);
scanf("%d",&arr[i]);
}

printf("\nEnter the number that has to be searched: ");
scanf("%d",&num);

beg=0;
end=n-1;
while(beg<=end)
{
mid=(beg end)/2;
if(arr[mid]==num)
{
printf("\n %d is present in the array at position = %d",num,mid);
found=1;
break;
}

if(arr[mid] > num)
end = mid-1;

else if(arr[mid] < num)
beg = mid+1;
}

if(beg > end && found==0)
printf("\n %d does not exist in the array",num);
getch();
}
```

This Code Is Quite Easy. First we take the no. of elements from the user and then user enter them. Then user inputs the element that has to be searched. Then we begin the searching. If the element to be found is the middle element, the element is shown, other wise for the two conditions, arr[mid] > num or arr[mid]  < num, the search iterates, either till the element is found or until the array gets terminated.

### Output:

Please Comment If You Liked This Post !!